{x}
blog image

All Elements in Two Binary Search Trees

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].
  • -105 <= Node.val <= 105

Solution Explanation: Merging Sorted Arrays from Two BSTs

This problem requires merging all the nodes from two Binary Search Trees (BSTs) into a single sorted array. Since BSTs, by definition, have an inherent sorted property (in-order traversal yields a sorted sequence), we can leverage this to create an efficient solution.

Approach:

  1. In-order Traversal: Perform an in-order traversal on both BSTs. In-order traversal visits nodes in the order: left subtree, root, right subtree. This ensures that the resulting arrays from both trees (a and b) will be sorted.

  2. Merge Sorted Arrays: Once we have two sorted arrays (a and b), we merge them using a two-pointer approach. This is a classic algorithm with linear time complexity. We iterate through both arrays simultaneously, comparing the current elements from each array. The smaller element is added to the result array, and the corresponding pointer is incremented. After one array is exhausted, we simply append the remaining elements of the other array.

Code Explanation (Python as an Example):

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        def dfs(root: TreeNode, nums: List[int]):
            if root is None:
                return
            dfs(root.left, nums)
            nums.append(root.val)
            dfs(root.right, nums)
 
        a, b = [], []
        dfs(root1, a)
        dfs(root2, b)
        # ... (merge logic as shown in the original response) ...

  • dfs(root, nums): This recursive helper function performs the in-order traversal. It recursively visits the left subtree, adds the current node's value to the nums list, and then recursively visits the right subtree.

  • a, b = [], []: Two empty lists are initialized to store the in-order traversal results of root1 and root2 respectively.

  • The merge logic (the while loops) efficiently combines the sorted arrays a and b into the final sorted ans list.

Time Complexity:

  • In-order traversal of each BST takes O(n) and O(m) time, where n and m are the number of nodes in the respective trees.
  • Merging two sorted arrays takes O(n+m) time.

Therefore, the overall time complexity is O(n + m).

Space Complexity:

  • The space complexity is dominated by the size of the arrays a, b, and ans. Each array can have at most n+m elements.
  • The recursive dfs function uses space proportional to the height of the trees (in the worst case, O(n) and O(m) for skewed trees, but O(log n) and O(log m) on average for balanced trees).

Therefore, the overall space complexity is O(n + m). In the case of balanced BSTs, the space complexity of the recursion becomes O(log n + log m), but the space for storing the results still dominates.

Other Languages:

The same approach applies to other programming languages (Java, C++, Go, TypeScript, Rust), with minor syntactic differences in the code but the core algorithm remains the same. The provided solutions in the original response demonstrate this consistency across languages.