Google Interview Question
Software Engineer / DevelopersCountry: United States
This solution does not meet the requirement of space not exceeding the height of the taller tree. Pushing initially all the left nodes of both BST's onto the stacks already breaks that limitation.
@Anonymous on May 19, 2012
Please write the complete code and run!
The code is running perfectly and there is no exception to be occurred! As the s1 has been checked already whether it is empty or not! If both empty then break; otherwise check for s2.
@Psycho - take tree 1 as:
9
6 13
5 7 10 14
tree 2 as:
4
3 5
now pass "t2,t1" as parameters. You'll have an exception when stack 1 gets empty but stack 2 still has elements...
Following the steps of @sqw with slight modifications
#include <cstdio>
#include <cstdlib>
#include <stack>
using namespace std ;
typedef struct node {
int val ;
struct node *left ;
struct node *right ;
}node ;
node* getNode (int value) {
node *element ;
element = (node *) malloc (sizeof(node)) ;
element->val = value ;
element->left = NULL ;
element->right = NULL ;
return element ;
}
void bstSort (node* root1, node* root2) {
stack<node*> s1, s2 ;
while (true) {
while (root1) {
s1.push (root1) ;
root1 = root1->left ;
}
while ( root2 ) {
s2.push (root2) ;
root2 = root2->left ;
}
if ( s1.empty() && s2.empty() )
break ;
if ( !s1.empty() && (s2.empty() || s1.top()->val < s2.top()->val)) {
root1 = s1.top () ;
printf ( "%d ", s1.top()->val ) ;
s1.pop () ;
root1 = root1->right ;
} else {
root2 = s2.top () ;
printf ( "%d ", s2.top()->val ) ;
s2.pop () ;
root2 = root2->right ;
}
}
printf ( "\n" ) ;
}
int main () {
node *root1, *root2 ;
root1 = getNode (20) ;
root1->left = getNode (15) ;
root1->right = getNode (25) ;
root1->left->left = getNode (9) ;
root1->left->right = getNode (18) ;
root1->right->left = getNode (22) ;
root1->right->right = getNode (30) ;
root1->left->right->left = getNode (17) ;
root1->right->left->right = getNode (24) ;
root2 = getNode (10) ;
root2->left = getNode (5) ;
root2->right = getNode (20) ;
root2->left->left = getNode (1) ;
root2->left->right = getNode (8) ;
root2->left->right->left = getNode (7) ;
bstSort (root2, root1);
return 0 ;
}
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;
}
}
I think it's also worth to review how to traverse a tree pre-order, in-order, post-order "iteratively".
The following is my implementation together with a basic test.
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 IterativeTraversal
{
public static void main(String[] args)
{
double[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
Node tree = createTree(array);
System.out.println(tree);
System.out.println(preorder(tree));
System.out.println(inorder(tree));
System.out.println(postorder(tree));
}
public static String preorder(Node root)
{
Stack<Node> stack = new Stack<Node>();
Node current = root;
StringBuffer sb = new StringBuffer();
while (null != current || !stack.isEmpty())
{
if (null != current)
{
sb.append(current.data + " ");
stack.push(current);
current = current.lChild;
continue;
}
current = stack.pop();
current = current.rChild;
}
return sb.toString().trim();
}
public static String inorder(Node root)
{
Stack<Node> stack = new Stack<Node>();
Node current = root;
StringBuffer sb = new StringBuffer();
while (null != current || !stack.isEmpty())
{
if (null != current)
{
stack.push(current);
current = current.lChild;
continue;
}
current = stack.pop();
sb.append(current.data + " ");
current = current.rChild;
}
return sb.toString().trim();
}
public static String postorder(Node root)
{
Stack<Node> stack = new Stack<Node>();
Node current = root;
StringBuffer sb = new StringBuffer();
while (null != current || !stack.isEmpty())
{
if (null != current)
{
if (null != current.rChild) {stack.push(current.rChild);}
stack.push(current);
current = current.lChild;
continue;
}
current = stack.pop();
if (stack.isEmpty())
{
sb.append(current.data + " ");
current = null;
continue;
}
if (stack.peek() != current.rChild)
{
sb.append(current.data + " ");
current = null;
continue;
}
stack.pop();
stack.push(current);
current = current.rChild;
}
return sb.toString().trim();
}
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;
}
@maverick you approach has a flaw:
suppose p1->data > p2->data but p1 has no left child than your algo will print p1->data
before p2->data which is obviously incorrect. However I find your idea quite original.. and tried to develop it further. I tested my approach on a number of examples, it seems to work fine. The pseudocode is below. Counterexamples are welcome)
struct node {
int val;
node *left;
node *right;
};
node *append(node *parent, int which, int val) {
node *x = new node;
x->left = x->right = 0;
x->val = val;
//
if(parent != 0) {
if(which == 0)
parent->left = x;
else
parent->right = x;
}
return x;
}
void traverse(node *t1, node *t2) {
//
if(t2 == 0) {
if(t1 == 0)
return;
traverse(t1->left, 0);
printf("%d ", t1->val);
traverse(t1->right, 0);
return;
}
//
if(t1 == 0) {
traverse(0, t2->left);
printf("%d ", t2->val);
traverse(0, t2->right);
return;
}
//
traverse(t1->left, t2->left);
if(t1->val >= t2->val) {
printf("%d ", t2->val);
node *s = t1->left;
t1->left = 0;
traverse(t1, t2->right);
t1->left = s;
} else {
printf("%d ", t1->val);
node *s = t2->left;
t2->left = 0;
traverse(t1->right, t2);
t2->left = s;
}
}
void destroy_tree(node *root) {
//
if(root == 0)
return;
destroy_tree(root->left);
destroy_tree(root->right);
delete root;
}
int main(){
node *x, *y;
node *head = append(0, 0, 10);
node *l = append(head, 0, 5),
*r = append(head, 1, 25),
*ll = append(l, 0, 3),
*lr = append(l, 1, 7);
append(lr, 0, 6);
//
node *head2 = append(0, 0, 7);
l = append(head2, 0, 6);
r = append(head2, 1, 11);
ll = append(l, 0, 1);
node *rr = append(r, 0, 9);
traverse(head, head2);
//
destroy_tree(head);
destroy_tree(head2);
}
this code is not correct on trees like
tree1:
node *head = append(0, 0, 5);
node *l = append(head, 0, 3),
*r = append(head, 1, 9),
*ll = append(l, 0, 1),
*lr = append(l, 1, 4);
tree2:
node *head = append(0, 0, 7);
node *l = append(head, 0, 6),
*r = append(head, 1, 10),
*ll = append(r, 0, 8),
*lr = append(r, 1, 11);
If the p1->data > p2->data but p1 has no left child, then just print the entire left sub-tree of p2 (using inorder traversal), then print p2 and then proceed to right sub-tree of p2. let me know if there are any flaws in this approach.
The Above Approach Failed in following BST, giving 2,4, 1 as output.
T1:
1
/ \
/ \
NULL NULL
T2:
4
/ \
/ NULL
2
/ \
/ \
NULL NULL
The solution above is wrong. There are enough cases presented above which prove that. Wondering, why people are voting for it ?
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;
}
}
1 small correction
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);
while(!stack.isEmpty()){
System.out.println(stack.pop().data);
}
}
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.
That will make it n * log (m) time, where n is number of elements in smaller tree... They want a soln in O(n) time.
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
Correct...
I appreciate your sol in the form of algo..... short sweet and simple....
Thanks
Doesn't meet the requirement of space tough...
I think the best solution is to stay with the recursive inorder algorithm and adapt it for 2 trees. This also works if one of the tree is empty.
void inorder(Node* t1, Node* t2)
{
if(t1 == NULL && t2 == NULL) return;
inorder(t1 && t1->left ? t1->left : NULL, t2 && t2->left ? t2->left : NULL);
if(t1 && t2)
{
if(t1->data < t2->data)
std::cout << t1->data << " " << t2->data << " ";
else
std::cout << t2->data << " " << t1->data << " ";
}
else
{
if(t1) std::cout << t1->data << " ";
if(t2) std::cout << t2->data << " ";
}
inorder(t1 && t1->right ? t1->right : NULL, t2 && t2->right ? t2->right : NULL);
}
your solution is taking O(n) space complexity. But in question it is mentioned the it should be of the order of logn.
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).
I agree with your algorithm.But it will take O( n ) space. We can only use O(log n ) space.
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);
}
}
}
i believe your solution wouldn't work because after the comparison of the two root values, you aren't breaking up one of the trees such that it is no longer pointing to its left subtree.
A simple counterexample for your solution is trying two trees such as 2 (without any children) and 1-3(root)-5. I believe your solution will print an incorrect solution.
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.
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);
}
}
- sqw May 19, 2012