30. Merge Two BSTs

The problem can be found at the following link: Question Link

Problem Description

Given two binary search trees (BST), merge them into a sorted array of elements from both trees.

The function should return elements of both BSTs in sorted form.

Examples:

Input:

BST1:

       5
     /   \
    3     6
   / \
  2   4

BST2:

        2
      /   \
     1     3
            \
             7
            /
           6

Output: 1 2 2 3 3 4 5 6 6 7

Explanation: After merging and sorting the two BSTs, we get 1 2 2 3 3 4 5 6 6 7.

My Approach

1. In-order Traversal of Both Trees:

   • We perform an in-order traversal on both BSTs to obtain two sorted arrays from the tree elements.

2. Merging Two Sorted Arrays:

   • The two sorted arrays obtained from the in-order traversals are merged into one sorted array using the two-pointer approach.

3. No Additional Tree Modifications:

   • We don't need to modify the structure of the trees, and the result can be generated by combining and sorting the tree elements.

4. Push Left Nodes:

   • To perform efficient merging of two trees without converting them into arrays first, use two stacks to store the nodes and process them similarly to how we merge two linked lists.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(m + n), where m is the number of nodes in BST1 and n is the number of nodes in BST2, as each node is visited exactly once.

• Expected Auxiliary Space Complexity: O(h1 + h2), where h1 and h2 are the heights of BST1 and BST2, because the recursion stack will store nodes up to the height of each tree during traversal.

Code (C++)

class Solution {
public:
    void pushLeft(Node* root, stack<Node*>& stk) {
        while (root) {
            stk.push(root);
            root = root->left;
        }
    }

    vector<int> merge(Node* root1, Node* root2) {
        vector<int> result;
        stack<Node*> s1, s2;
        pushLeft(root1, s1);
        pushLeft(root2, s2);

        while (!s1.empty() || !s2.empty()) {
            if (s2.empty() || (!s1.empty() && s1.top()->data <= s2.top()->data)) {
                Node* node = s1.top();
                s1.pop();
                result.push_back(node->data);
                pushLeft(node->right, s1);
            } else {
                Node* node = s2.top();
                s2.pop();
                result.push_back(node->data);
                pushLeft(node->right, s2);
            }
        }
        return result;
    }
};

Code (Java)

class Solution {
    private void pushLeft(Node root, Stack<Node> stack) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public List<Integer> merge(Node root1, Node root2) {
        List<Integer> result = new ArrayList<>();
        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();
        pushLeft(root1, s1);
        pushLeft(root2, s2);

        while (!s1.isEmpty() || !s2.isEmpty()) {
            if (s2.isEmpty() || (!s1.isEmpty() && s1.peek().data <= s2.peek().data)) {
                Node node = s1.pop();
                result.add(node.data);
                pushLeft(node.right, s1);
            } else {
                Node node = s2.pop();
                result.add(node.data);
                pushLeft(node.right, s2);
            }
        }
        return result;
    }
}

Code (Python)

class Solution:
    def pushLeft(self, root, stack):
        while root:
            stack.append(root)
            root = root.left

    def merge(self, root1, root2):
        result = []
        s1, s2 = [], []
        self.pushLeft(root1, s1)
        self.pushLeft(root2, s2)

        while s1 or s2:
            if not s2 or (s1 and s1[-1].data <= s2[-1].data):
                node = s1.pop()
                result.append(node.data)
                self.pushLeft(node.right, s1)
            else:
                node = s2.pop()
                result.append(node.data)
                self.pushLeft(node.right, s2)

        return result

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit my LinkedIn:- Any Questions. Thank you for your input; together, we strive to create a space where learning is a collaborative endeavor.

⭐ Star this repository if you find it helpful or intriguing! ⭐

---

📍Visitor Count