Merge Two BST

Difficulty: Medium

Asked in: Amazon, Microsoft, Google

Given two binary search trees with root nodes as tree1 and tree2 of size n and m , write a program to return an array of integers that contains all the elements of tree1 and tree2 in non-decreasing order.

Problem Note

The expected time complexity is O( m+n ).

Example 1

Input:      3            4        
           / \          / \
          2   5        1   6
Output: [1, 2, 3, 4, 5, 6]
Explanation: The resultant binary tree contains all the elements of bst1 and bst2 in non-decreasing order.

Example 2

Input:      3            6        
             \          / \
              4        2  10
Output:[2, 3, 4, 6, 10]
Explanation: Both bst1 and bst2 are combined to return the BST having all the elements of bst1 and bst2 in non-decreasing order.

Solutions

We will be discussing various solutions to this problem. Before that, you should be familiar with the properties of Binary Search Trees. Read Here.

Naive Solution : Traverse on both the trees separately while storing them in respective arrays and then store each element in the 3rd array and return it after sorting.
Sorted Merge: Inorder traversal of both trees will give two sorted arrays. Use the merge function of the merge sort to return the sorted array after merging them.
Using Stacks: While inorder traversal, maintain two stacks that will store the current smallest element on the top for each tree and on that basis maintain the result array.

The TreeNode passed to the function will be:

class TreeNode{
    TreeNode left
    int val
    TreeNode right
}

Give this problem a try on your own.

1. Naive Solution

The problem asks us to return the value of each node in a sorted array. So, the simplest way to solve this problem is to traverse the trees and store each of their node values in the respective two auxiliary arrays.

Create a result array and put all of the values from two auxiliary arrays inside it and then return the array after sorting it.

Solutions Steps

Create two arrays arr1 and arr2.
Perform inorder traversal on both BST while adding node value in arr1 and arr2 for each visit.
Insert all the values of arr1 and arr2 in result array.
Sort the result array and return it.

Pseudo Code

int[] getAllElements(TreeNode root1,TreeNode root2) {
    int[] arr1
    int[] arr2
    inorder(root1, arr1)
    inorder(root2, arr2)
    int[] result
    for(i =0 to i < arr1.size()) {
        result.push_back(arr1[i])
    }
    for(i =0 to i < arr2.size()) {
        result.push_back(arr2[i])
    }
    result.sort()
    return result
}
// inorder traversal
void inorder(TreeNode root, int[] arr) {
    if(root) {
        inorder(root.left)
        arr.push_back(root.val)
        inorder(root.right)
    }
}

Complexity Analysis

Time Complexity : O(n log n), where n is the total number of nodes of tree1 and tree2.

Space Complexity : O(n)

Critical Ideas To Think

Do we use any property of BST?
Will this approach work if the tree is a binary tree instead of a binary search tree. If yes, Why?
Why do we sort the result array before returning it?
Can we do preorder or postorder traversal, instead of in-order traversal? Will the result array be affected by any traversal in this approach?

2. Sorted Merge

A very important property of BST is that, when we do in-order traversal on BST, we get a sorted array.

In this problem, we can use the above property as the problem demands us to return a sorted array. So, we can perform in-order traversal of both the BSTs and we will get two sorted arrays. Each of the arrays will contain all the node’s values of the respective BST.

Now, we have two sorted arrays, all we have to do is to merge them. If you have read about merge sort, then you would have known that during the “Combine” step, we merge two sorted arrays in linear time, Read here or Read here . Eventually, we will have the sorted result array and we could simply return it.

Solution Steps

Perform inorder traversal of tree1 and store each node’s value in arr1.
Perform inorder traversal of tree2 and store each node’s value in arr2.
Combine arr1 and arr2 using merge function of merge sort to create result array.
Return result array.

Pseudo Code

int[] getAllElements(TreeNode root1,TreeNode root2){
    int[] arr1
    int[] arr2
    inorder(root1, arr1)
    inorder(root2, arr2)
    int[] result
    merge(arr1, arr2, result)
    return result       
}
// utility Functions
void inorder(TreeNode root, int[] arr){
    if(root){
        inorder(root.left)
        arr.push_back(root.val)
        inorder(root.right)
    }
}
void merge(int[] X, int[] Y, int[] result){
    int i = 0, j = 0
    while(i < X.size() and j < Y.size()){
        if(X[i] > Y[j]){
            result.push_back(Y[j])
            j = j + 1
        } else {
            result.push_back(X[i])
            i = i + 1
        }
    }
    while(i < X.size()){
        result.push_back(X[i])
        i = i + 1
    }
    while(j < Y.size()){
        result.push_back(Y[j])
        j = j + 1
    }
}

Complexity Analysis

Time Complexity : O(n), where n is the total number of nodes of tree1 and tree2 .

Space Complexity : O(n) (Why?)

Critical Ideas To Think

What is the time complexity of inserting all nodes value in arr during in-order traversal?
How is the array sorted after the in-order traversal of BST?
How did we merge both the arrays in linear time?
Can you optimize the space complexity?

3. Using Stacks

Let’s think again about BST, we know that any element on the left side of the root is always going to be smaller than the root. And in this problem, to merging the two tree nodes, we can compare the two nodes of both the trees while adding into the result array simultaneously.

So, at any point in time, the comparisons that will be required to construct the result array will only be from those nodes which lie in the path from the root to the current node.

We can create two stacks for each tree and will maintain the stack as the smallest element on the top. Now, considering we have two stacks where the stack is sorted in ascending order from top to bottom, we can simply compare the top of both the stacks and put smaller ones in the result array, thereby popping up that element from the stack.

In this way, we could reduce memory usage as the maximum size of the stack will reach equal to the height of the tree. If the BST is height-balanced BST, then this approach will significantly affect the space complexity.

Solution Steps

Create two stacks, stack1 and stack2
Iterate until tree1 is not NULL or tree2 is not NULL or stack1 is not empty or stack2 is not empty.
For each iteration:

Push all the left nodes of tree1 inside stack1
Push all the left nodes of tree2 inside stack2
Compare the top of both the stacks, put the smaller one in the result while popping it out from the respective stack and move to its right child.

Return result

Pseudo Code

int[] getAllElements(TreeNode root1,TreeNode root2) {
    stack1 = Stack()
    stack2 = Stack()
    tree1 = root1
    tree2 = root2
    int[] result
    while(tree1 or tree2 or stack1 or stack2) {
        while (tree1) {
            stack1.push(tree1)
            tree1 = tree1.left
        }
        while (tree2) {
            stack2.push(tree2)
            tree2 = tree2.left
        }
        if (not stack2) or (stack1 and stack1.top().val <= stack2.top().val) {
            tree1 = stack1.pop()
            result.push_back(tree1.val)
            tree1 = tree1.right
        }
        else {
            tree2 = stack2.pop()
            result.push_back(tree2.val)
            tree2 = tree2.right
        }
    }
    return result
}

Complexity Analysis

Time Complexity : O(n), where n is the total number of nodes of tree1 and tree2 .

Space Complexity : O(n), If the BST is height-balanced BST, then it’s O(log n)

Critical Ideas To Think

In the above code, there is a nested while loop. So, how the time complexity is O(n)?
How did we make sure that the stack at any point in time must be sorted from top to bottom?
Why do we put all the left nodes inside the stacks at once and then compared the top of the stacks?
Dry the run the above code on example1 and example2 and verify how our approach works!