CareerCup

Should be trivial.
1. Pick one of the trees, call it left tree, and then traverse the right tree, from root.
2. When we traverse a node from the right tree, we insert into the left tree.

a. If you allowed to use extra memory.
1. Convert tree1 and tree2 into sorted arrays by in-order traversal - O(N+M)
2. Merge arrays into one sorted array - O(N+M)
3. Make BST from merged array in a divide-and-conquer manner -O(N+M)
Total - O(M+N)
b. If you must consume a constant memory
Take all elements from first bst and inser into second. It will take O(M log (M+N) ) computaions.

public class MergeBinarySearchTrees {

    private static class Node {
        
        private Node left;
        private Node right;
        private int payload;
        
        public String toString() {
            StringBuilder sb = new StringBuilder();
            
            sb.append("(");
            sb.append(payload);
            
            if (left != null) sb.append(left);
            if (right != null) sb.append(right);
            
            sb.append(")");
            
            return sb.toString();
        }
    }
    
    public static void main(String[] args) {
        
        Node n60 = new Node(); n60.payload = 60;
        Node n45 = new Node(); n45.payload = 45;
        
        Node n30 = new Node(); n30.payload = 30;
        Node n15 = new Node(); n15.payload = 15;
        Node n5 = new Node();  n5.payload = 5;
        
        Node n50 = new Node(); n50.payload = 50; n50.left = n45; n50.right = n60;
        Node n40 = new Node(); n40.payload = 40; n40.left = n30; n40.right = n50;
        
        Node n10 = new Node(); n10.payload = 10; n10.left = n5; n10.right = n15;
        
        Node n20 = new Node(); n20.payload = 20; n20.left = n10; n20.right = n40;
        
        Node n2 = new Node(); n2.payload = 2;
        Node n7 = new Node(); n7.payload = 7;
        Node n14 = new Node(); n14.payload = 14;
        Node n18 = new Node(); n18.payload = 18;
        
        Node n4 = new Node(); n4.payload = 4; n4.left = n2; n4.right = n7;
        Node n16 = new Node(); n16.payload = 16; n16.left = n14; n16.right = n18;
        
        Node n12 = new Node(); n12.payload = 12; n12.left = n4; n12.right = n16;
        
        System.out.println(merge(n20, n12));
    }
    
    private static Node merge(Node n1, Node n2) {
        
        List<Node> todo = new LinkedList<Node>();
        todo.add(n1);
        while(!todo.isEmpty()) {
            Node n = todo.remove(0);
            if (n.left != null) {
                todo.add(0, n.left);
                n.left = null;
            }
            if (n.right != null) {
                todo.add(1, n.right);
                n.right = null;
            }          
            inject(n, n2);
        }
        
        return n2;
    }
    
    private static void inject(Node n, Node n2) {
        if (n.payload >= n2.payload) {
            if (n2.right == null) {
                n2.right = n;
                return;
            }
            // otherwise
            if (n.payload >= n2.right.payload) { 
                inject(n, n2.right);
                return;
            }
            // otherwise
            if (n2.right.left == null) {
                n2.right.left = n;
                return;
            }
            // otherwise
            if (n.payload <= n2.right.left.payload) {
                inject(n, n2.right.left);
                return;
            }
            // otherwise
            Node temp = n2.right.left;
            n2.right.left = n;
            n.left = temp;
            return;
        }
        
        // otherwise
        if (n2.left == null) {
            n2.left = n;
            return;
        }
        // otherwise
        if (n.payload < n2.left.payload) {
            inject(n, n2.left);
            return;
        }
        // otherwise
        if (n2.left.right == null) {
            n2.left.right = n;
            return;
        }
        // otherwise
        if (n.payload >= n2.left.right.payload) {
            inject(n, n2.left.right);
            return;
        }
        // otherwise
        Node temp = n2.left.right;
        n2.left.right = n;
        n.right = temp;
        return;
    }
}