CareerCup

public static void print2BSTInorder(Node n1, Node n2) {
        Stack<Node> stack1 = new Stack<Node>();
        Stack<Node> stack2 = new Stack<Node>();
 
        while (true) {
            while (n1 != null) {
            	stack1.push(n1);
            	n1 = n1.left;
            } 
            while (n2 != null) {
            	stack2.push(n2);
            	n2 = n2.left;
            }
            if (stack1.isEmpty() && stack2.isEmpty()) break;
            if (stack2.isEmpty() || stack1.peek().value < stack2.peek().value) {
                n1 = stack1.pop();
                System.out.print(n1.value+",");
                n1 = n1.right;
            } else {
                n2 = stack2.pop();
                System.out.print(n2.value+",");
                n2 = n2.right;
            }
        }
        System.out.println();
    }

The following is my implementation together with a basic test.
I would appreciate any counterexample you might found.

import java.util.*;

class Node
{
 public Node lChild = null;
 public Node rChild = null;
 public double data;
 public Node(double d) {data = d;}
 public String toString()
 {
  return "{" + ((null == lChild) ? "" : lChild) + data + ((null == rChild) ? "" : rChild) + "}";
 }
}

class G208
{
 public static String merge(Node A, Node B)
 {
  Stack<Node> parentA = new Stack<Node>();
  Stack<Node> parentB = new Stack<Node>();
  Node currentA = A;
  Node currentB = B;
  StringBuffer sb = new StringBuffer();

  while (!parentA.isEmpty() || null != currentA || !parentB.isEmpty() || null != currentB)
  {
   if (null != currentA)
   {
    parentA.push(currentA);
    currentA = currentA.lChild;
    continue;
   }

   if (null != currentB)
   {
    parentB.push(currentB);
    currentB = currentB.lChild;
    continue;
   }

   double dataA = Double.POSITIVE_INFINITY;
   if (!parentA.isEmpty()) {dataA = parentA.peek().data;}

   double dataB = Double.POSITIVE_INFINITY;
   if (!parentB.isEmpty()) {dataB = parentB.peek().data;}

   if (dataA < dataB)
   {
    sb.append(dataA + " ");
    currentA = parentA.pop();
    currentA = currentA.rChild;
   }
   else
   {
    sb.append(dataB + " ");
    currentB = parentB.pop();
    currentB = currentB.rChild;
   }
  }

  return sb.toString().trim();
 }

 public static void main(String[] args)
 {
  double[] array1 = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
  double[] array2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  Node tree1 = createTree(array1);
  Node tree2 = createTree(array2);
  System.out.println(tree1);
  System.out.println(tree2);
  System.out.println(merge(tree1, tree2));
 }

 public static Node createTree(double[] array)
 {
  return createTree(array, 0, array.length - 1);
 }

 private static Node createTree(double[] array, int begin, int end)
 {
  if (begin > end) {return null;}
  if (begin == end) {return new Node(array[begin]);}
  int size = end - begin + 1;
  int lSize = (size - 1) / 2;
  Node n = new Node(array[begin + lSize]);
  n.lChild = createTree(array, begin, begin + lSize - 1);
  n.rChild = createTree(array, begin + lSize + 1, end);
  return n;
 }
}

void BinarySearchTree::inorder(tree_node* p1,tree_node* p2)
{
    if((p1 != NULL)||(p2 !=NULL))
    {
		if(p1->data > p2->data)
		{
			if(p1->left) inorder(p1->left,p2);
			cout<<" "<<p1->data<<" ";
			if(p1->right) inorder(p1->right,p2);
		}
		else
		{
			if(p2->left) inorder(p1,p2->left);
			cout<<" "<<p2->data<<" ";
			if(p2->right) inorder(p1,p2->right);
		}
    }
    else return;
}

package binaryTreeQuestions;

import java.util.Stack;

public class TwoBSTPrinter {

private static Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();

public static void printSorted(BinaryTreeNode bst1,BinaryTreeNode bst2){
pushIntoStack(bst1);
printInorder(bst2);
}

private static void printInorder(BinaryTreeNode bst){
if(bst==null){
return;
}

printInorder(bst.left);
while(!stack.isEmpty() && bst.data>stack.peek().data){
System.out.println(popFromStack());
}
System.out.println(bst.data);
printInorder(bst.right);
}

private static void pushIntoStack(BinaryTreeNode node){
if(node!=null){
stack.push(node);
pushIntoStack(node.left);
}
}

private static int popFromStack(){
BinaryTreeNode node=stack.pop();
pushIntoStack(node.right);
return node.data;
}
}

Basically same approach as the top-rated one above, except hopefully cleaner:
(1) First, push all the elements from root to the left-most leaf node onto a stack. Do this for both trees
(2) Peek at the top element of each stack (if non-empty) and print the smaller one.
(3) Pop the element off the stack that contains the element we just print
(4) Add the right child of the element we just popped onto the stack, as well as all its left descendants

void printSorted(Node n, Node n2) {
	Stack<Node> nodes = new Stack<Node>();
	Stack<Node> nodes2 = new Stack<Node>();
	insertNodes(n, nodes);
	insertNodes(n2, nodes2);

	while(!nodes.isEmpty() || !nodes2.isEmpty()) {
		int a = (nodes.isEmpty() ? Integer.MAX_VALUE : nodes.peek().value);
		int b = (nodes2.isEmpty() ? Integer.MAX_VALUE : nodes2.peek().value);
		if(a < b) {
			System.out.print(a);
			insertNodes(nodes.pop().right, nodes);
		} else {
			System.out.print(b);
			insertNodes(nodes2.pop().right, nodes2);
		}
	}
}

void insertNodes(Node n, Stack<Node> nodes) {
	while(n != null) {
		nodes.push(n);
		n = n.left;
	}
}

I think you can do this problem by just inserting second tree elements on first tree and then do inorder traveral. Now finally you will get sorted numbers.

assume we have an array A equal to the number of elements (n) in the larger binary tree ..
a[0] ... a[n-1]

1) Do an in-order traversal of the elements in the larger bst and store it in the array in sorted order

2) set index1=0

3) process each element in the second bst by doing an in-order traversal

while processing each element

a) if index1=n print the element
b) else if the element is smaller than a[index1] print the element
c) else
print all the elements in a which are less than the current element and increment index1 for each element printed (Handle boundary condition index!=n before each check)

Complexity O(n) where n is the total number of elements in both the trees

If you get two iterators for the trees using an in-order DFS traversal, then compare values all the way to the end, then won't you be handling at most O(height of bigger tree) in memory? Don't forget that O(height of bigger tree) = O(height of bigger tree + height of smaller tree), since the height of the bigger tree dominates the height of the smaller tree.

T(h1,h2) = O(h1 + h2) ==> T(h1,h2) <= c*(h1+h2), and if h2 < h1, ch1 + ch2 < 2ch1, ergo O(h1+h2) = O(h1)

Please confirm algorithm.

To print the elements of a BST in sorted order, you do an in-order tree traversal iteration, that is, you visit its left child first, then its parent, then its right child. This is because left child value will be < parent value which is < right child value.

Because you have 2 BST's in which the next smallest value could be in either tree, you compare the next smallest element in each tree via the in-order traversal. Whichever is smallest, output that and go to the next node.

This will guarantee you a list of sorted elements with linear time O(n).

Convert both the trees into inplace DLL. O(n)
Now merge both the DLL O(n)

Print the list O(n)

Total time O(n)

We can do a inorder traversal of large tree storing it in array of length of the large tree.
We can do a inorder traversal of smaller tree with a static index which keeps track of elements in array if large tree. Now while doing inorder traversal of small tree compare the value of smaller element being visited to current static index in large array of large tree if value in smaller tree is less print else print values from large tree which are less and accordingly increment the index.
We have space complexity of O(n) where n is the no of nodes in Large tree and space complexity is O(m+n). where n is the no of nodes in Large tree and m is the no of nodes in Small tree.

I think this solution follows all the conditions. The key here is that you have to write the inorder traversal using stacks so that you can control the traversal.

package interview.tree;

import java.util.Iterator;
import java.util.Stack;

public class BST
{
    static class Node
    {
        private int data;
        private Node left;
        private Node right;

        public Node(final int data)
        {
            this.data = data;
        }

        public Node(final int data, final Node left, final Node right)
        {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public int getData()
        {
            return data;
        }

        public Node getLeft()
        {
            return left;
        }

        public Node getRight()
        {
            return right;
        }
    }

    static class NodeMetadata
    {
        private Node node;
        private boolean traversed;

        public NodeMetadata(final Node node)
        {
            this.node = node;
            this.traversed = false;
        }

        public Node getNode()
        {
            return node;
        }

        public void traversed()
        {
            this.traversed = true;
        }

        public boolean isTraversed()
        {
            return this.traversed;
        }
    }

    public static void merge(final Node t1, final Node t2)
    {
        BstIterator i1 = new BstIterator(t1);
        BstIterator i2 = new BstIterator(t2);

        int d1 = -1, d2 = -1;
        while(i1.hasNext() && i2.hasNext())
        {
            d1 = i1.next().getData();
            while (i2.hasNext() && ((d2 = i2.next().getData()) <= d1))
            {
                System.out.print(d2 + " ");
            }
            System.out.print(d1 + " ");
            System.out.print(d2 + " ");
        }
        while(i1.hasNext())
        {
            System.out.print(i1.next().getData() + " ");
        }
        while(i2.hasNext())
        {
            System.out.print(i2.next().getData() + " ");
        }
    }

    static class BstIterator implements Iterator<Node>
    {
        private Stack<NodeMetadata> s = new Stack<NodeMetadata>();

        public BstIterator(final Node head)
        {
            s.push(new NodeMetadata(head));
        }

        @Override
        public boolean hasNext()
        {
            return !s.empty();
        }

        @Override
        public Node next()
        {
            NodeMetadata cur;
            while (!s.empty())
            {
                cur = s.pop();
                if (cur.isTraversed())
                {
                    return cur.getNode();
                }
                else
                {
                    if (cur.getNode().getRight() != null)
                    {
                        s.push(new NodeMetadata(cur.getNode().getRight()));
                    }
                    cur.traversed();
                    s.push(cur);
                    if (cur.getNode().getLeft() != null)
                    {
                        s.push(new NodeMetadata(cur.getNode().getLeft()));
                    }
                }
            }
            return null;
        }

        @Override
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }

    public static void main(String[] args)
    {
        Node t1 = new Node(3, new Node(1), new Node(5));
        Node t2 = new Node(4, new Node(2), new Node(6));
        
        // BstIterator i1 = new BstIterator(t1);
        // while(i1.hasNext())
        // {
        // System.out.print(i1.next().getData() + " ");
        // }
        // System.out.println();

        // BstIterator i2 = new BstIterator(t2);
        // while(i2.hasNext())
        // {
        // System.out.print(i2.next().getData() + " ");
        // }
        // System.out.println();
        
        merge(t1, t2);
    }
}

typedef struct btnode_{
	int index;
	int val;
	struct btnode_ *left, *right;
	bool visited;
	btnode_():val(0),
			index(0),
			left(NULL),
			right(NULL),
			visited(false){};
	explicit btnode_(int _val):val(_val),
					index(0), 
					left(NULL), 
					right(NULL), 
					visited(false){};
}BTNODE;

void print_two_bst_inorder(BTNODE *t1, BTNODE *t2){
	if(!t1 || !t2) {
		print_inorder(t1);
		print_inorder(t2);
		return;
	}
	stack<BTNODE *> t1s;
	stack<BTNODE *> t2s;
	t1s.push(t1);
	t2s.push(t2);
	while(!t1s.empty()&&!t2s.empty()){
		t1=t1s.top();
		t2=t2s.top();
		if(t1->left && !t1->left->visited){
			t1s.push(t1->left);
		} else if(t2->left && !t2->left->visited){
			t2s.push(t2->left);
		}
		/*t1 and t2 and smallest in current subtree*/
		else if(t1->val<t2->val){
			cout<<t1->val<<endl;
			t1->visited=true;
			t1s.pop();
			if(t1->right && !t1->right->visited){
				t1s.push(t1->right);
			}
		} else {
			cout<<t2->val<<endl;
			t2->visited=true;
			t2s.pop();
			if(t2->right && !t2->right->visited){
				t2s.push(t2->right);
			}
		}	
	}
	while(!t1s.empty()){
		t1=t1s.top();
		if(t1->left && !t1->left->visited){
			t1s.push(t1->left);
		} else {
			cout<<t1->val<<endl;
			t1->visited=true;
			t1s.pop();
			if(t1->right && !t1->right->visited){
				t1s.push(t1->right);
			}
		}
	}
	while(!t2s.empty()){
		t2=t2s.top();
		if(t2->left && !t2->left->visited){
			t2s.push(t2->left);
		} else {
			cout<<t2->val<<endl;
			t2->visited=true;
			t2s.pop();
			if(t2->right && !t2->right->visited){
				t2s.push(t2->right);
			}
		}
	}
}

inorder_trees(Node* root1, Node* root2){
   if(root1 == NULL && root2 == NULL){
      return;
   }

   else if(root1 != NULL && root2 == NULL){
            inorder_trees(root1->left, NULL);
            printf("%d\t", root1->data);
            inorder_trees(root1->right, NULL);
   }
   else if(root1 == NULL && root2 != NULL){
            inorder_trees(NULL, root2->left);
            printf("%d\t", root2->data);
            inorder_trees(NULL, root2->right);
   }
else{
    if(root1 -> data  <=  root2 -> data)
       inorder_trees(root1, root2->left);
    else
       inorder_trees(root1 -> left, root2);
 }
}

Using two stacks(use each one to find the successors of the nodes) the time will be O(n + m) and space will be O(logn + logm)
Here is the java implementation:

//with stack
 public void printAscStack(TreeNode t1, TreeNode t2) {
 Stack<TreeNode> s1 = new Stack();
 Stack<TreeNode> s2 = new Stack();
 
 while (!(t1 == null && t2 == null && s1.isEmpty() && s2.isEmpty)) {
  if (t1 != null && t2 != null) {
   s1.push(t1);
   s2.push(t2);
   t1 = t1.left;
   t2 = t2.left;
  } else if (t1 != null) {
   s2.push(t1);
   t1 = t1.left;
  } else if (t2 != null) {
   s2.push(t2);
   t2 = t2.left;
  } else {
   if (!s1.isEmpty() && !s2.isEmpty) {
    if (s1.peek.data.compareTo(s2.peek.data) < 0) {
     t1 = s1.poll();
     System.out.println(t1.data);
     t1 = t1.right;
    } else {
     t2 = s2.poll();
     System.out.println(t2.data);
     t2 = t2.right;
    }
   } else if (!s1.isEmpty()) {
    t1 = s1.poll();
    System.out.println(t1.data);
    t1 = t1.right;
   } else {
    t2 = s2.poll();
    System.out.println(t2.data);
    t2 = t2.right;
   }
  }
 }
 }

I thinks this should work

void merge(BSTNode* tree1,BSTNode* tree2) {
	if(tree1 == NULL && tree2 == NULL) {
		
	}
	else if(tree1 == NULL) {
		inorder(tree2);
	}
	else if(tree2 == NULL) {
		inorder(tree1);
	}
	else {
		if(tree1->data < tree2->data) {
			merge(tree1->left,tree2->left);
			printf(" %d %d ",tree1->data,tree2->data);
			merge(tree1->right,tree2->right);
		}
		else {
			merge(tree2->left,tree1->left);
			printf(" %d %d ",tree2->data,tree1->data);
			merge(tree2->right,tree1->right);
		}
	}
}

Assume T1 has n1 nodes and T2 has n2 nodes. To achieve O(n1+n2) is really easy.

1. Preorder traverse T1, add each node to stack1.
2. Preorder traverse T2, add each node to stack2.
3. Pop one node from each of T1 and T2, t1 and t2, compare t1 and t2:
if (t1 < t2)
print t1
t1 = T1.pop()
else
print t2
t2 = T2.pop()

until one stack is empty, then just print out the rest of the other stack.

Convert the tree into DDL and then simply print the two lists.

use non-recursive traversal tree with DFS.. max space needed is height of big tree

Hello everyone, how does the following solution look? I believe it will print the correct answer without extra memory but it will destroy parts of the tree :p

public void doSomething(Node root1, Node root2)
{
if (root1 == null && root2 == null)
{
return;
}else if (root1 == null)
{
printInOrder (root2);
}else if (root2 == null)
{
printInOrder (root1);
}else
{
if (root1.data < root2.data)
{
//doSomething on first root's left subtree and second root's left subtree
doSomething(root1.left, root2.left);

System.out.println(root1.data);

//doSomething on first right subtree and second right subtree including root but excluding second left subtree
root2.left = null;
doSomething(root1.right, root2);
}else
{
doSomething(root1.left, root2.left);

System.out.println(root2.data);

root1.left = null; //same logic as before
doSomething(root1, root2.right);


}
}

testing ....as i m new to this site :)

right

	data
	
			view