# Teaching Kids Programming – All Elements in Two Binary Search Trees (Parallel Iterative Inorder Traversal Algorithm)

#### Bydinesh

May 2, 2022

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^5

Hints:
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 $tex_d211875c13c4f4a13d5a054366b8e602 Teaching Kids Programming - All Elements in Two Binary Search Trees (Parallel Iterative Inorder Traversal Algorithm) algorithms DFS python teaching kids programming youtube video$ 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).

GD Star Rating

Source