Problem

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

Examples

Example 1:

graph LR

    subgraph r1["root1"]
        B(2) --- A(1) & D(4)
    end
    
    subgraph r2["root2"]
        A2(0) --- B2(1) & C1(3)
    end
    
    r1 ~~~ r2
  
1
2

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

graph LR

    subgraph r1["root1"]
        A(1) ~~~ N1:::hidden
        A --- H(8)
    end
    
    subgraph r2["root2"]
        H2(8) --- A2(1)
	    H2 ~~~ N2:::hidden
    end
    
    r1 ~~~ r2

classDef hidden display:none
  
1
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

Solution

Method 1 – Inorder Traversal + Merge Sorted Lists

Intuition

Both trees are binary search trees (BSTs), so an inorder traversal of each tree gives a sorted list of their elements. Merging two sorted lists is straightforward and efficient.

Approach

  1. Perform an inorder traversal on root1 to get a sorted list l1.
  2. Perform an inorder traversal on root2 to get a sorted list l2.
  3. Merge l1 and l2 into a single sorted list ans using the two-pointer technique.
  4. Return ans.

Edge Cases:

  • If either tree is empty, return the inorder traversal of the other tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
  void inorder(TreeNode* n, vector<int>& v) {
    if (!n) return;
    inorder(n->left, v);
    v.push_back(n->val);
    inorder(n->right, v);
  }
  vector<int> getAllElements(TreeNode* r1, TreeNode* r2) {
    vector<int> l1, l2, ans;
    inorder(r1, l1);
    inorder(r2, l2);
    int i = 0, j = 0;
    while (i < l1.size() && j < l2.size()) {
      if (l1[i] < l2[j]) ans.push_back(l1[i++]);
      else ans.push_back(l2[j++]);
    }
    while (i < l1.size()) ans.push_back(l1[i++]);
    while (j < l2.size()) ans.push_back(l2[j++]);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  void inorder(TreeNode n, List<Integer> v) {
    if (n == null) return;
    inorder(n.left, v);
    v.add(n.val);
    inorder(n.right, v);
  }
  public List<Integer> getAllElements(TreeNode r1, TreeNode r2) {
    List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>(), ans = new ArrayList<>();
    inorder(r1, l1);
    inorder(r2, l2);
    int i = 0, j = 0;
    while (i < l1.size() && j < l2.size()) {
      if (l1.get(i) < l2.get(j)) ans.add(l1.get(i++));
      else ans.add(l2.get(j++));
    }
    while (i < l1.size()) ans.add(l1.get(i++));
    while (j < l2.size()) ans.add(l2.get(j++));
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
  def getAllElements(self, r1: 'TreeNode | None', r2: 'TreeNode | None') -> list[int]:
    def inorder(n: 'TreeNode | None') -> list[int]:
      if not n: return []
      return inorder(n.left) + [n.val] + inorder(n.right)
    l1 = inorder(r1)
    l2 = inorder(r2)
    ans: list[int] = []
    i = j = 0
    while i < len(l1) and j < len(l2):
      if l1[i] < l2[j]:
        ans.append(l1[i])
        i += 1
      else:
        ans.append(l2[j])
        j += 1
    ans.extend(l1[i:])
    ans.extend(l2[j:])
    return ans

Complexity

  • ⏰ Time complexity: O(n + m) where n and m are the number of nodes in root1 and root2.
  • 🧺 Space complexity: O(n + m) for storing the inorder traversals and the merged list.