CareerCup

Guys here is the answer. I have tested too. It works. I have used a combination of iteration and recursion.
1) inside the iteration, get the next leaf element from each tree (using getFirstLeafInorder) and compare, if it is not equal return false here and stop.
2) from the iteration (while loop) , call a function getFirstLeafInorder that uses stack that stacks nodes and also status of nodes (00 - no subtrees visited, 01 - Left subtree would be visited, 11- right subtree would be visited) and inorder traversal to determine the next leaf element and return
3) If all the leaf elements are same, in the iteration both leaf elements would be -999(a flag that says tree is completely in order traversed), return true

public static boolean checkLeafSequenceSame(Node root1, Node root2){
if(root1 == null && root2 == null)
return true;
if((root1 == null && root2 != null) || (root1 != null && root2 == null))
return false;

Stack<NodeStatus> stack1 = new Stack<NodeStatus>();
Stack<NodeStatus> stack2 = new Stack<NodeStatus>();

stack1.push(new NodeStatus(root1, 00));
stack2.push(new NodeStatus(root2,00));

boolean toReturn = false;



while(true){
int number1 = getFirstLeafInorder(stack1, root1);
int number2 = getFirstLeafInorder(stack2, root2);

System.out.println("Numbers compared "+number1+" "+number2);

if(number1 != number2){
toReturn = false;
break;
}
else if(number1 == -999 && number2 == -999){
toReturn = true;
break;
}
else if((number1 == -999 && number2 != -999)||(number1 != -999 && number2 == -999)) {
toReturn = false;
break;
}

}

return toReturn;
}


private static int getFirstLeafInorder(Stack<NodeStatus> stack, Node root){
NodeStatus top = stack.peek();
Node node = top.nodeTraversed;
if(node == null){
stack.pop();
return getFirstLeafInorder(stack,root);
}





//got the leaf element
if(node.left == null && node.right == null){
stack.pop();
return node.data;
}


int number = -99;
int status = top.status;
if(status == 00){
top.status = 01;
stack.push(new NodeStatus(node.left,00));
number = getFirstLeafInorder(stack, root);


}
else if(status == 01){
top.status = 11;
stack.push(new NodeStatus(node.right,00));
number = getFirstLeafInorder(stack, root);

}
else if(status ==11 ){
if(node == root)
return -999;
stack.pop();
number = getFirstLeafInorder(stack, root);

}

return number;

}



Node class and a Wrapper class that stores Node and status
=========
public class Node{
int data;
Node left;
Node right;
Node(int _data, Node _left, Node _right){
data = _data;
left = _left;
right = _right;

}
}


public class NodeStatus{
public Node nodeTraversed;
public int status;

public NodeStatus(Node _nodeTraversed, int _status){
nodeTraversed = _nodeTraversed;
status = _status;

}


}

Let me if you need clarification anywhere.
unfortunately, I was not able to come up with this exact algorithm on the spot in the interview, it was a new problem for me.

Can you define what sequence it is?

Assuming that

5
/ \
2 7

and
5
/ \
Null 3
/ \
2 7
should result to false , as for 2nd tree 1st leaf is Null where as not for the 1st tree . Algo can be as following taking help of some extra mem ( a Queue ) .

1) traverse the first tree in any manner you wish ( BFS, DFS, inorder etc ) whenever you encounter a leaf enqueue into the queue . Please keep in mind if you find one node which is not a leaf does contain a Null child then also you need to enqueue that NUll child ( may be some Custom Node representation of NULL, say -1)

2) Now traverse the 2nd tree in the same fashion & for every leaf node dequeue the tree . If both the leaf & dequeued node are same ( including the NULL elem's check ) go ahead , else break from the check .

3) if all goes well , i.e, no break inbetween , both the tree's are short circuited else not .

Hope I am able to explain my Algo.

if multithreading is allowed.. a simpler approach will be

maintain a global queue for both of them to write the leaves they have observed so far..

two counts, 1 count to let know the number of leaves observed in tree A so far and 2 count to let know the number of leaves observed in tree B so far.
> each thread runs parallelly and once it finds a leaf, checks whether the other tree's leaf for that count fetched the same result. If no set a flag to quit. If yes, continue traversing the tree. > If the other tree hasn't found the leaf of that count yet.. simply add to the queue the value that this thread observed.

The threads end when all leaves are compared or it reached the end traversing the tree.. edge cases of thread's number of leaves differing can be checked too..

Single thread approach..

I see single thread approach to be a one check at a time approach.. fetch the first leaf of the tree A, compare it with the tree B's first leaf.. if yes go to the next leaf comparison..


I may be wrong.. but this is what i see it to be ..

if multithreading is allowed.. a simpler approach will be

maintain a global queue for both of them to write the leaves they have observed so far..

two counts, 1 count to let know the number of leaves observed in tree A so far and 2 count to let know the number of leaves observed in tree B so far.
> each thread runs parallelly and once it finds a leaf, checks whether the other tree's leaf for that count fetched the same result. If no set a flag to quit. If yes, continue traversing the tree. > If the other tree hasn't found the leaf of that count yet.. simply add to the queue the value that this thread observed.

The threads end when all leaves are compared or it reached the end traversing the tree.. edge cases of thread's number of leaves differing can be checked too..

Single thread approach..

I see single thread approach to be a one check at a time approach.. fetch the first leaf of the tree A, compare it with the tree B's first leaf.. if yes go to the next leaf comparison..


I may be wrong.. but this is what i see it to be ..

I think the solution is very simple. Do a PreOrder Traversal on the trees (one at a time). While doing the traversal, if you hit a node that has node.Left == null and node.Right == null (leaf node), then add it to a linked list. After we traverse both the trees, we will have two linked lists (holding references to leaf nodes). Now just iterate and compare the lists. If any node does not match, return false.

It can be determined by doing the DFS of each tree and as soon as get the unmatched leaf return false.

bool CheckSameLeafSeq(node *n1, node *n2){
    if (NULL == n1 && NULL == n2){
        return true;
    } else if (NULL == n1 || NULL == n2 ){
        return false;
    } else {
        using namespace std;
        stack<node*> s1, s2;
        node *a, *b; 
        s1.push(n1);
        s2.push(n2);

        while (!s1.empty() && !s2.empty()){
            while(!s1.empty()){
                a = s1.top();
                s1.pop();

                if(a->left == NULL && a->right == NULL){
                    break;
                } else {
                    if (a->right) s1.push(a->right);
                    if (a->left) s1.push(a->left);
                }
            }

            while(!s2.empty()){
                b = s2.top();
                s2.pop();

                if(b->left == NULL && b->right == NULL){
                    break;
                } else {
                    if (b->right) s2.push(b->right);
                    if (b->left) s2.push(b->left);
                }
            }

            if (a->value != b->value){
                return false;
            }
        }

        if (!s1.empty() || !s2.empty()){
            return false;
        }
    }

    return true;
}

Do an inorder traversal on both trees and when leaf is hit check if both matches and continue else break .

public boolean compareLeaf(Node tree1, Node tree2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while(tree1!=null || stack1.isEmpty() || tree2!=null || stack2.isEmpty()) {
Node t1=null, t2=null;
while(tree1!=null || !stack1.isEmpty()) {

if(tree1!=null) {
stack1.push(tree1);
tree1= tree1.left;
}
else {
Node n = stack1.pop();
if(n.left==null && n.right==null) {
t1=n;
tree1 =n.right;
break;
}
else {
tree1 = n.right;
}

}
}

while(tree2!=null || !stack2.isEmpty()) {

if(tree2!=null) {
stack2.push(tree2);
tree2= tree2.left;
}
else {
Node n = stack2.pop();
if(n.left==null && n.right==null) {
t2=n;
tree2 = n.right;
break;
}
tree2 = n.right;

}
}
if(t1.value!=t2.value) {
return false;
}


}
return true;
}

public boolean compareLeaf(Node tree1, Node tree2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while(tree1!=null || stack1.isEmpty() || tree2!=null || stack2.isEmpty()) {
Node t1=null, t2=null;
while(tree1!=null || !stack1.isEmpty()) {

if(tree1!=null) {
stack1.push(tree1);
tree1= tree1.left;
}
else {
Node n = stack1.pop();
if(n.left==null && n.right==null) {
t1=n;
tree1 =n.right;
break;
}
else {
tree1 = n.right;
}

}
}

while(tree2!=null || !stack2.isEmpty()) {

if(tree2!=null) {
stack2.push(tree2);
tree2= tree2.left;
}
else {
Node n = stack2.pop();
if(n.left==null && n.right==null) {
t2=n;
tree2 = n.right;
break;
}
tree2 = n.right;

}
}
if(t1.value!=t2.value) {
return false;
}


}
return true;
}

public boolean compareLeaf(Node tree1, Node tree2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while(tree1!=null || stack1.isEmpty() || tree2!=null || stack2.isEmpty()) {
Node t1=null, t2=null;
while(tree1!=null || !stack1.isEmpty()) {

if(tree1!=null) {
stack1.push(tree1);
tree1= tree1.left;
}
else {
Node n = stack1.pop();
if(n.left==null && n.right==null) {
t1=n;
tree1 =n.right;
break;
}
else {
tree1 = n.right;
}

}
}

while(tree2!=null || !stack2.isEmpty()) {

if(tree2!=null) {
stack2.push(tree2);
tree2= tree2.left;
}
else {
Node n = stack2.pop();
if(n.left==null && n.right==null) {
t2=n;
tree2 = n.right;
break;
}
tree2 = n.right;

}
}
if(t1.value!=t2.value) {
return false;
}


}
return true;
}

public boolean compareLeaf(Node tree1, Node tree2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while(tree1!=null || stack1.isEmpty() || tree2!=null || stack2.isEmpty()) {
Node t1=null, t2=null;
while(tree1!=null || !stack1.isEmpty()) {

if(tree1!=null) {
stack1.push(tree1);
tree1= tree1.left;
}
else {
Node n = stack1.pop();
if(n.left==null && n.right==null) {
t1=n;
tree1 =n.right;
break;
}
else {
tree1 = n.right;
}

}
}

while(tree2!=null || !stack2.isEmpty()) {

if(tree2!=null) {
stack2.push(tree2);
tree2= tree2.left;
}
else {
Node n = stack2.pop();
if(n.left==null && n.right==null) {
t2=n;
tree2 = n.right;
break;
}
tree2 = n.right;

}
}
if(t1.value!=t2.value) {
return false;
}


}
return true;
}

public boolean compareLeaf(Node tree1, Node tree2) {
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while(tree1!=null || stack1.isEmpty() || tree2!=null || stack2.isEmpty()) {
Node t1=null, t2=null;
while(tree1!=null || !stack1.isEmpty()) {

if(tree1!=null) {
stack1.push(tree1);
tree1= tree1.left;
}
else {
Node n = stack1.pop();
if(n.left==null && n.right==null) {
t1=n;
tree1 =n.right;
break;
}
else {
tree1 = n.right;
}

}
}

while(tree2!=null || !stack2.isEmpty()) {

if(tree2!=null) {
stack2.push(tree2);
tree2= tree2.left;
}
else {
Node n = stack2.pop();
if(n.left==null && n.right==null) {
t2=n;
tree2 = n.right;
break;
}
tree2 = n.right;

}
}
if(t1.value!=t2.value) {
return false;
}


}
return true;
}

Why can't we use Level Order Traversal for both trees maintaining two queues for each tree for their respective leafs. This way we will always find the first leaf at the earliest and then we can compare and break or continue(short circuit) accordingly.

bool AreAllLeavesSame( NODE tree1, NODE tree2 )
{
	NODE leafFromTree1, leafFromTree2;
	_stack stack1, stack2;
	NODE visited1, visited2;
	do
	{
		leafFromTree1 = returnNextLeaf( tree1, stack1, visited1 );
		leafFromTree2 = returnNextLeaf( tree2, stack2, visited2 );
		if( leafFromTree1 != leafFromTree2 )
			return false;
	}while( leafFromTree1 != NULL && leafFromTree2 != NULL );
	return true;
}
NODE returnNextLeaf( NODE &p, _stack &stack, NODE &visited )
{
	do
	{
		if( visited == p->left )
			while( p != NULL )
			{
				stack.push(p);
				p=p->left;
			}
						
		if( !empty.stack() )
		{
			temp = stack.top();
			if( temp->right == NULL || visited == temp->right )
				visit(temp);
				visited = temp;
				stack.pop();
			else
				p = p->right;
		}
		if( visited->left == NULL && visited->right == NULL )
			return visited;
	}while( p != NULL || !stack.empty() );
	return NULL;
}

You need to connect the leafs of each tree such like
every right child of leaf should point to the next leaf in DFS order and then how still we would be able to find out whether its a leaf or not for that their left child will
point to the node itself. Then after doing this both the trees have all leafs connected then we just to reach first leaf of both and compare.

I would use iterative way to traverse both trees. In addition, I need two queues to store the leaf nodes in a sequential order for each tree. As traversal, if neither queues is empty, then de-queue both, and compare the two nodes. If the nodes are different, then return false; else go on traversal.