All Elements in Two Binary Search Trees

Problem Statement

In the provided problem, we are given two binary search trees, labeled as root1 and root2. The task is to merge the values from both trees into a single list, ensuring that the values are sorted in ascending order. This requires handling the binary search tree properties efficiently to achieve the desired result. The trees can have varying numbers of nodes, potentially being empty, and the values within the nodes can range broadly from -105 to 105.

Examples

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

Approach and Intuition

The challenge is to efficiently combine and sort the data from two binary search trees (BSTs). The main properties of BSTs that we leverage are:

1. Inorder traversal of a BST yields the elements in sorted order.

Steps to Solve:

1. Perform an inorder traversal on both root1 and root2:

   • The inorder traversal accesses the left subtree, the node itself, and then the right subtree. This will give us all elements from each tree in ascending order.

2. Merge the two sorted lists obtained:

   • Use a two-pointer technique to merge these two lists in a similar fashion to merging two sorted arrays. This ensures the merged list is also sorted.

Efficiency Consideration:

• The inorder traversal of a BST is O(n), where n is the number of nodes in the tree. Since we perform this twice (once for each tree) and then merge the two lists, which is another O(n), the overall complexity remains linear relative to the total number of elements in both trees.
• Since the combined output list needs to hold every element from both trees, the space complexity is also O(n), where n is the sum of nodes in both trees.

This method is straightforward given the properties of BST and leverages efficient list merging techniques, ensuring that even with the maximum constraint of 5,000 nodes per tree, the operation would be feasible within a reasonable timeframe.

Solutions

class Solution {
  public List<Integer> retrieveAllElements(TreeNode node1, TreeNode node2) {
    ArrayDeque<TreeNode> deque1 = new ArrayDeque(), deque2 = new ArrayDeque();
    List<Integer> result = new ArrayList();

    while (node1 != null || node2 != null || !deque1.isEmpty() || !deque2.isEmpty()) {
      // Traverse left until possible
      while (node1 != null) {
        deque1.push(node1);
        node1 = node1.left;
      }
      while (node2 != null) {
        deque2.push(node2);
        node2 = node2.left;
      }

      // Compare the nodes from top of stacks and process
      if (deque2.isEmpty() || !deque1.isEmpty() && deque1.getFirst().val <= deque2.getFirst().val) {
        node1 = deque1.pop();
        result.add(node1.val);
        node1 = node1.right;
      } else {
        node2 = deque2.pop();
        result.add(node2.val);
        node2 = node2.right;
      }
    }
    return result;
  }
}