Teaching Kids Programming: Videos on Data Structures and Algorithms
Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]Example 2:
Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8]Constraints:
The number of nodes in each tree is in the range [0, 5000].
-10^5 <= Node.val <= 10^5Hints:
Traverse the first tree in list1 and the second tree in list2.
Merge the two trees in one list and sort it.
Naive Bruteforce Inorder and Sort
We can traverse both binary search trees in any order, and then combine to a list and sort it. This will take 
time where N, M are the number of the nodes for two binary search trees respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]: def dfs(root): if not root: return [] return dfs(root.left) + [root.val] + dfs(root.right) a, b = dfs(root1), dfs(root2) return sorted(a + b) |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
def dfs(root):
if not root:
return []
return dfs(root.left) + [root.val] + dfs(root.right)
a, b = dfs(root1), dfs(root2)
return sorted(a + b)
Inorder and Merge Algorithm
Since these two trees are BST, we can perform the inorder traversal which gives us two sorted list – then we can merge them via O(N+M) time.
The inorder can be easily implemented (trivially) via Recursion (Depth First Search Algorithm):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]: def dfs(root): if not root: return [] return dfs(root.left) + [root.val] + dfs(root.right) a, b = dfs(root1), dfs(root2) la, lb = len(a), len(b) i = j = 0 ans = [] while i < la and j < lb: if a[i] < b[j]: ans.append(a[i]) i += 1 else: ans.append(b[j]) j += 1 if i < la: ans.extend(a[i:]) if j < lb: ans.extend(b[j:]) return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
def dfs(root):
if not root:
return []
return dfs(root.left) + [root.val] + dfs(root.right)
a, b = dfs(root1), dfs(root2)
la, lb = len(a), len(b)
i = j = 0
ans = []
while i < la and j < lb:
if a[i] < b[j]:
ans.append(a[i])
i += 1
else:
ans.append(b[j])
j += 1
if i < la:
ans.extend(a[i:])
if j < lb:
ans.extend(b[j:])
return ans
We need two passes: first pass is the inorder Teaching Kids Programming – Binary Tree Inorder Traversal via Recursion or Iteration, and then merge two sorted list How to Merge Two Sorted Lists (Recursion and Iterative)?.
Iterative Parallel Inorder of Two Binary Search Tree
The Inorder can be implemented via Iterative algorithm, see below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: ans = [] st = [] while root or st: while root: st.append(root) root = root.left root = st.pop() ans.append(root.val) root = root.right return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
st = []
while root or st:
while root:
st.append(root)
root = root.left
root = st.pop()
ans.append(root.val)
root = root.right
return ans
We need to push the left to the stack and go to left as much as we can. Then we take one from the stack and try the right route. With these, we can do two inorder at the same time with two stacks. We need to pop whichever is smaller.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]: st1, st2, ans = [], [], [] while st1 or st2 or root1 or root2: while root1: st1.append(root1) root1 = root1.left while root2: st2.append(root2) root2 = root2.left if not st2 or (st1 and st1[-1].val < st2[-1].val): root1 = st1.pop() ans.append(root1.val) root1 = root1.right else: root2 = st2.pop() ans.append(root2.val) root2 = root2.right return ans |
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
st1, st2, ans = [], [], []
while st1 or st2 or root1 or root2:
while root1:
st1.append(root1)
root1 = root1.left
while root2:
st2.append(root2)
root2 = root2.left
if not st2 or (st1 and st1[-1].val < st2[-1].val):
root1 = st1.pop()
ans.append(root1.val)
root1 = root1.right
else:
root2 = st2.pop()
ans.append(root2.val)
root2 = root2.right
return ans
The advantage is the single pass – despite it having the same time/space complexity: O(N+M).
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
901 words
Last Post: Teaching Kids Programming - Typing Characters with Backspace (Text Editor Algorithm via Stack)