Merging 2 Binary Search Trees

I was thinking on different ways to merge 2 given binary search trees (BSTs). One thought is to flatten each tree into separate array or list using pre-order traversal. Then merge 2 sorted arrays/lists into 1 and then create a tree from it. This can be done in O(m+n) time. Instead, this post shows how can we merge them with O(log (m+n)) time. Below is the Java code to demonstrate it.

public class Merge2BST {
 TreeNode merged = null;
 static TreeNode add (TreeNode TreeNode, int data) {
    if (TreeNode == null) {
      return new TreeNode (data);
    }
    else if (data < TreeNode.data) {
      TreeNode.left = add (TreeNode.left, data);
    }
    else if (data > TreeNode.data) {
      TreeNode.right = add (TreeNode.right, data);
    }
    return TreeNode;
 }
 static TreeNode merge (int d1, int d2, TreeNode mergedNode) { 
   if (d1 < d2) {
     mergedNode = add (mergedNode, d1);
     mergedNode = add (mergedNode, d2);
   } else {
     mergedNode = add (mergedNode, d2);
     mergedNode = add (mergedNode, d1);
   }
   return mergedNode;
 }
 TreeNode mergeBST (TreeNode TreeNode1, TreeNode TreeNode2) {
   if (TreeNode1 == null && TreeNode2 == null) {
    return null;
   }
   if (TreeNode1 == null && TreeNode2 != null) {
    return add (this.merged, TreeNode2.data);
   }
   
   if (TreeNode2 == null && TreeNode1 != null) {
    return add (this.merged, TreeNode1.data);
   }
   this.merged = merge (TreeNode1.data, TreeNode2.data, 
                         this.merged);
   mergeBST (TreeNode1.left, TreeNode2.left);
   mergeBST (TreeNode1.right, TreeNode2.right);
   return this.merged;
 }
 public static void main(String[] args) {
    Merge2BST o = new Merge2BST();
    // create BST 1
    TreeNode TreeNode1 = new TreeNode (5);
    TreeNode1.left = new TreeNode (4);
    TreeNode1.right = new TreeNode (7);
    TreeNode1.right.right = new TreeNode (9);
    TreeNode1.right.left = new TreeNode (6);
    // create BST 2
    TreeNode TreeNode2 = new TreeNode (3);
    TreeNode2.left = new TreeNode (2);
    TreeNode2.right = new TreeNode (8);
    o.merged = o.mergeBST (TreeNode1, TreeNode2);
    o.print(o.merged);
 }
 void print (TreeNode TreeNode) {
   if (TreeNode == null) return;
   
   print (TreeNode.left);
   System.out.print(TreeNode.data+" ");
   print (TreeNode.right);
 }
}
class TreeNode {
  int data;
  TreeNode left, right;
  TreeNode (int data) {
    this.data = data;
  }
}

Binary Search Tree 1 and Binary Search Tree 2

Merged Binary Search Tree

In this code we create 2 BSTs. We pass 2 BSTs to mergeBST(). The mergeBST does pre order tree traversal and calls merge() with left subtree, right subtree and merged tree arguments. The recursion comes for our rescue to make the code concise and achieve our task. The calls add() and merge() are self -explanatory. The add() follows standard BST node addition functionality. And merge() calls add(). I think below call needs some explanation:

TreeNode mergeBST (TreeNode TreeNode1, TreeNode TreeNode2)

The recursive mergeBST(TreeNode1, TreeNode2) has 3 cases to return.

When TreeNode1 == null && TreeNode1 == null it returns null.

When TreeNode1 == null && TreeNode2 != null, we call add () and return

When TreeNode2 == null && TreeNode1 != null, we call add () and return

Else it keeps calling mergeBST() recursively.

This makes sure even if we have 2 trees with different heights the code takes care of adding respective node to the merged tree. Please note that the merged BST is not a balanced tree.

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

This is my first post on Medium. If you think anything is missing in the code, please let me know and I will try to run my test cases against it and rectify it accordingly. Thank you!