Merge two BST 's

JavaView on GFG

Time: O(n+m)

Space: O(n+m)

Intuition

Merge two BSTs into one balanced BST. In-order both to get sorted arrays, merge, build balanced BST.

Algorithm

1In-order traverse both BSTs to get sorted arrays. Merge two sorted arrays. Build balanced BST from sorted array.

Common Pitfalls

•Three steps: in-order (O(n)), merge (O(m+n)), build balanced BST (O(m+n)). Total O(m+n).

Merge two BST 's.java

Java

// Approach: In-order traverse both BSTs to get sorted arrays, merge the two sorted arrays, build balanced BST.
// Time: O(n+m) Space: O(n+m)
import java.util.*;

class Node {
    int data;
    Node left, right;

    public Node(int d) {
        data = d;
        left = right = null;
    }
}

class Solution {
    // Function to return a list of integers denoting the node
    // values of both the BST in a sorted order.
    public List<Integer> merge(Node root1, Node root2) {
        List<Integer> ans = new ArrayList<>();
        solve(root1, ans);
        solve(root2, ans);

        Collections.sort(ans);

        return ans;
    }

    private void solve(Node root, List<Integer> list) {
        if (root == null)
            return;

        solve(root.left, list);
        list.add(root.data);
        solve(root.right, list);
    }
}

Was this solution helpful?