Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
11
of 11 vote

struct node {
    int val;
    node *left,*right;
    node(int v):val(v),left(0),right(0) {}
};

class bst_iterator {
private:
    stack<node *> s;
public:
    bst_iterator(node *rt) {
        while (rt)
            s.push(rt),rt=rt->left;
    }
    bool has_next() {
        return !s.empty();
    }
    node *next() {
        node *c=s.top();
        s.pop();
        node *n=c->right;
        while (n)
            s.push(n),n=n->left;
        return c;
    }
};

bool same_inorder(node *a,node *b) {
    bst_iterator ita(a),itb(b);
    while (ita.has_next()&&itb.has_next()) {
        node *ca=ita.next();
        node *cb=itb.next();
        if (ca->val!=cb->val)
            return false;
    }
    return !ita.has_next()&&!itb.has_next();
}

- Anonymous April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Impressive !!

- LaithBasilDotNet May 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one!

- bhuleskar July 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

var Node = function (value) {
	this.value = value;
};

function StepTree(v) {
	var S = [];
	S.push(v);

	return {
		next: function () {
			while (S.length && S[S.length - 1].visited !== true) {
				v = S.pop();
				if (!v.visited) {
					v.visited = true;
					v.right && S.push(v.right);
					S.push(v);
					v.left && S.push(v.left);
				}
			} 
			return S.pop() || null;
		}
	};
}


function isSame(node1, node2) {
	return node1.value === node2.value;
}
function compareInorder(tree1, tree2) {
	tree1 = StepTree(tree1);
	tree2 = StepTree(tree2);

	var bool = true;
	var node1 = tree1.next();
	var node2 = tree2.next();
	
	while (bool && (node1 || node2)) {
		bool = isSame(node1, node2);
		node1 = tree1.next();
		node2 = tree2.next();
	}

	return bool;
}

var aA = new Node('A');
var aB = new Node('B');
var aC = new Node('C');
var bA = new Node('A');
var bB = new Node('B');
var bC = new Node('C');
aB.right = aA;
aB.left = aC;

bA.right = bB;
bB.right = bC;

compareInorder(aB, bA);

- srterpe April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node class

package binaryTree;

public class Node<T> {
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node<T> getLeft() {
		return left;
	}
	public void setLeft(Node<T> left) {
		this.left = left;
	}
	public Node<T> getRight() {
		return right;
	}
	public void setRight(Node<T> right) {
		this.right = right;
	}
	private T data;
	private Node<T> left;
	private Node<T> right;
}

package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Tree<T> {
	Node<T> root;
	
	public Tree(){
		
	}
	public Node<T> getRoot(){
		return root;
	}
	public void setRoot(T data){
		root = new Node<T>();
		root.setData(data);
	}
	
	public void addLeftChild(T par, T chld){
		Node<T> parNode = getNode(par);
		if(parNode != null){
			Node<T> leftNode = parNode.getLeft();
			if(leftNode == null){
				leftNode = new Node<T>();
				parNode.setLeft(leftNode);
			}
			leftNode.setData(chld);
		}
	}
	
	public void addRightChild(T par, T chld){
		Node<T> parNode = getNode(par);
		if(parNode != null){
			Node<T> rightNode = parNode.getRight();
			if(rightNode == null){
				rightNode = new Node<T>();
				parNode.setRight(rightNode);
			}
			rightNode.setData(chld);
		}
	}
	
	public Node<T> getNode(T data){
		return getNode(getRoot(), data);
	}
	public Node<T> getNode(Node<T> node, T data){
		if(node != null){
			if(node.getData().equals(data)){
				return node;
			}
			Node<T> leftNodeResult = getNode(node.getLeft(),data);
			if(leftNodeResult != null){
				return leftNodeResult;
			}
			Node<T> rightNodeResult = getNode(node.getRight(),data);
			if(rightNodeResult != null){
				return rightNodeResult;
			}
		}
		return null;
	}
	
	public void inOrder(Node<T> node,List<T> list){
		if(node != null){
			if(node.getLeft() != null){
				inOrder(node.getLeft(),list);
			}
			list.add(node.getData());
			if(node.getRight() != null){
				inOrder(node.getRight(),list);
			}
		}
	}
	
	public List<T> inOrder(){
		List<T> list = new ArrayList<T>();
		inOrder(root,list);
		return list;
	}
	
	public boolean isSameInorder(Tree<T> other){
		Iterator<T> thisListIter = inOrder().iterator();
		Iterator<T> otherListIter = other.inOrder().iterator();
		while(thisListIter.hasNext() && otherListIter.hasNext()){
			if (thisListIter.next() != otherListIter.next()){
				return false;
			}
		}
		if(thisListIter.hasNext() || otherListIter.hasNext()){
			return false;
		}
		return true;
	}
}

Test code

package binaryTree;


public class SameInorder {
	public static void main(String[] args){
		Tree<String> t1 = new Tree<String>();
		t1.setRoot("B");
		t1.addLeftChild("B", "A");
		t1.addRightChild("B", "C");
		
		
		Tree<String> t3 = new Tree<String>();
		t3.setRoot("A");
		t3.addRightChild("A", "B");
		t3.addRightChild("B", "C");
		
		System.out.println(t1.isSameInorder(t3));
	}
}

- dadakhalandhar April 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node{
private int value;
private Node left;
private Node right;

public Node(int v)
{
this.value=v;
}
public Node(int v,Node l,Node r)
{
this.value=v;
this.left=l
this.right=r;
}
}


public class InOrderAssessor{


public boolean checkInOrder(Node a,Node b)
{
if(a==null && b==null)
{
return true;
}

String x=getInOrderString(a,"");
String y=getInOrderString(b,"");
return x.equals(y);
}


private void getInOrder(Node n,String s)
{
if(n==null)
{
return;
}
getInOrder(n.left.mp);
s+=n.value();
getInOrder(n.right,mp);
}


}

- Div April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterative in-order traversal will solve the problem.
have a method getNext(), which returns the next node value in in-order traversal. Use this value to compare the traversals of the trees.
getNext() can be implemented using a stack.

- brofessor April 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node {
    int val;
    node *left,*right;
    node(int v):val(v),left(0),right(0) {}
};

class bst_iterator {
private:
    stack<node *> s;
public:
    bst_iterator(node *rt) {
        while (rt)
            s.push(rt),rt=rt->left;
    }
    bool has_next() {
        return !s.empty();
    }
    node *next() {
        node *c=s.top();
        s.pop();
        node *n=c->right;
        while (n)
            s.push(n),n=n->left;
        return c;
    }
};

bool same_inorder(node *a,node *b) {
    bst_iterator ita(a),itb(b);
    while (ita.has_next()&&itb.has_next()) {
        node *ca=ita.next();
        node *cb=itb.next();
        if (ca->val!=cb->val)
            return false;
    }
    return !ita.has_next()&&!itb.has_next();
}

- Anonymous April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey guys!
I've tried to make the compact OOP code for this problem using an InOrderIterator. Check it out:

public class SameInorderGoogle {

    private static class TreeNode {
        public final int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    private static class InOrderIterator implements Iterator<TreeNode> {
        private TreeNode curr;
        private Deque<TreeNode> stack = new LinkedList<>();
        public InOrderIterator(TreeNode root) { this.curr = root; }

        @Override public TreeNode next() {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode ret = stack.pop();
            curr = ret.right;
            return ret;
        }

        @Override public boolean hasNext() {
            return curr != null || !stack.isEmpty();
        }
    }

    public boolean compareInOrder(TreeNode r1, TreeNode r2) {
        InOrderIterator iterator1 = new InOrderIterator(r1);
        InOrderIterator iterator2 = new InOrderIterator(r2);
        while (iterator1.hasNext() && iterator2.hasNext())
            if (iterator1.next().val != iterator2.next().val) return false;
        return true;
    }
}

- andreytim April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You forgot to check if the binary trees have the same number of elements. Also it looks like compareInOrder should be static.

- Michael May 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder iterator class with the driver function to compare output for both iterator.

package prep;

import java.util.Stack;

public class InorderIterator {
	Stack<Node> st = new Stack<Node>();
	Node root;
	Node nextNode = null;
	
	public InorderIterator(Node root) {
		this.root = root;
	}
	
	public boolean hasnext(){
		if(nextNode != null) return true;
		Node cur = null;
		if(st == null) return false;
		if(!st.empty())
			cur = st.pop();
		else{
			cur = root;
		}
		while(true){
			if(cur != null){
				st.push(cur);
				cur = cur.left;
			}else{
				if(!st.isEmpty()){
					Node tmp = st.pop();
					if(nextNode == null){
						nextNode = tmp;
					}
					st.push(tmp.right);
					tmp = tmp.right;
					return true;
				}else{
					st= null;
					return false;
				}
			}
		}
	}
	
	public Node next(){
		if(nextNode != null){
			Node tmp = nextNode;
			nextNode = null;
			return tmp;
		}
		if(hasnext()){
			Node tmp = nextNode;
			nextNode = null;
			return tmp;
		}else{
			new Exception("Element not found");
		}
		
		return nextNode;
	}
}

public boolean sameInorder(Node root1,Node root2){
    	   	InorderIterator itr1 = new InorderIterator(root1);
    	   	InorderIterator itr2 = new InorderIterator(root2);
	   		while(itr1.hasnext() && itr2.hasnext()){
	   			if(itr1.next().value != itr2.next().value){
	   				return false;
	   			}
	   		}
	   		if((!itr1.hasnext() && itr2.hasnext()) || (itr1.hasnext() && !itr2.hasnext())){
	   			return false;
	   		}
	   		return true;
       }

- mabansal April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool compare(Node *a, Node *b) {

	stack<Node*> x, y;
	// Find the first elements
	while (a) {
		x.push(a);
		a = a->left;
	}
	while (b) {
		y.push(b);
		b = b->left;
	}
	// Walk the trees
	while (!x.empty() && !y.empty()) {
		a = x.top(); x.pop();
		b = y.top(); y.pop();

		if (a->value != b->value) {
			return false;
		}
		// Find next node on tree a
		if (a->right) x.push(a = a->right);
		while (a->left) {
			x.push(a = a->left);
		}
		// Find next node on tree b
		if (b->right) y.push(b = b->right);
		while (b->left) {
			y.push(b = b->left);
		}
	}
	return x.empty() && y.empty();
}

- nikolay.dimitrov April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do inorder traversal for both tree and keep the output in a queue. When trying to add item from inorder of first tree check if output from second queue is empty. If queue is not empty, remove that item from second queue.
Worst case O(m + n) : Both tree fully traversed and Best case: O(max(log m, log n)) : First item in the tree don't match.

Code:
public <T> boolean inorder(Util.Tree<T> t1, Util.Tree<T> t2, Queue<T> res1, Queue<T> res2) {
if (t1 == null && t2 == null) {
return true;
}
if (!inorder((t1 != null ? t1.left : null), (t2 != null ? t2.left : null), res1, res2)) {
return false;
}
if (t1 != null) {
if (!add(t1.value, res1, res2)) {
return false;
}
}
if (t2 != null) {
if (!add(t2.value, res2, res1)) {
return false;
}
}
if (!inorder((t1 != null ? t1.right : null), (t2 != null ? t2.right : null), res1, res2)) {
return false;
}
return true;
}

public <T> boolean solve(Util.Tree<T> t1, Util.Tree<T> t2) {
LinkedTransferQueue<T> res1 = new LinkedTransferQueue<T>();
LinkedTransferQueue<T> res2 = new LinkedTransferQueue<T>();
return inorder(t1, t2, res1, res2) && res1.isEmpty() && res2.isEmpty();
}

- nikunj.iitk May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean isSameInorder(b1,  b2)
{
	stack : s1;
	stack : s2;
	while(b1 ! =null)
	{
		s1.push(b1);
		b1 =b1.left;
	}


	while(b2 ! =null)
	{
		s2.push(b2);
		b2 =b2.left;
	}

	while((s1 && s2 )!=null)
	{
		node a = s1.pop();
		node b = s2.pop();
		if(a.data == b.data)
		{
			return false;
		}
		a = a.right;
		b = b.right;
		while(a!=null)
		{
			s1.push(a);
			a = a.left;
		}

		while(b!=null)
		{
			s2.push(b);
			b = b.left;
		}
	}
	return true;
}

- vipul May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int isSameInorder(Node* root1, Node* root2){
	Stack<Node*> st1,st2;
	Node* iter1=root1;
	Node* iter2=root2;
	do{
		while(iter1!=NULL){
		  st1.push(iter1);
		  iter1=iter1->left;
		}
		while(iter2!=NULL){
		  st2.push(iter2);
		  iter2=iter2->left;
		}
		Node* temp1 = st1.pop();
		Node* temp2 = st2.pop();
		if(temp1->value != temp2->value) return false;
		iter1=temp1->right;
		iter2=temp2->right;
	}while(!st1.empty() && ! st2.empty());
	if(st1.empty() && st2.empty())
		return true;
	else
		return false;
}

- harsv May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Usually we use Stack to do iterative InOrder traversal. With 2 binary trees, we certainly have to use at least 2 stacks.
The each tree has its own traversal steps, the order of PUSH a node in the corresponding stack will not be the same. However, in oder to have the same InOrder, the POP from the corresponding stack must be in the same order.

So, we can use a variable to keep track of that. Iteratively traversal Tree1 only if the variable is null and stop every time a Node is poped out of Stack1. Start traversal the Tree2 from there until a Node is poped out, if it's the same as the Node from Tree1, set the variable to null again.

Something like this:

public static boolean check(Node root1, Node root2) {
		Stack<Node> stack1 = new Stack<Node>();
		Node current1 = root1;
		
		Stack<Node> stack2 = new Stack<Node>();
		Node current2 = root2;
		
		Node popedNode = null;
		
		while(true) {
			if(popedNode == null) {
				if(current1 != null) {
					stack1.push(current1);
					current1 = current1.left;
				} else {
					if(!stack1.isEmpty()) {
						popedNode = stack1.pop();
						current1 = popedNode.right;
					} else {
						break;
					}
				}
			} else { //popedNode != null, has been assigned above
				if(current2 != null) {
					stack2.push(current2);
					current2 = current2.left;
				} else {
					if(!stack2.isEmpty()) {
						Node n = stack2.pop();
						if(n.value == popedNode.value) {
							System.out.println(n.value);
							popedNode = null; //continue travel Tree1
						}
						else
							return false;
						current2 = n.right;
					} else {
						break;
					}
				}
			}
			
			
		}

		if(!stack1.isEmpty() || stack2.isEmpty())
				return false;
		return true;
	}

- Minh Hoang May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach: Keep two List for Inorder traversal of each tree. Traverse both tree in inorder parallel and keep updating the inorder list. Whenever adding new element, check top of the small is same to corresponding larger list. Break early whenever inorder is not same.
In the worst case list size will grow as many number of nodes in both tree.
In best case it will detect as early possible without much memory usage.

Here is the C# code with Test driver

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Given two binary trees ( not BST) ,   return true if both of them have same inorder  else return false.
    /// Approach: Keep to List for Inorder traversal of each tree. Whenver adding new element, check top of the small is same to corresponding larger list.
    /// Break early whenever inorder is not same. In the worst case list size will grow as many number of nodes in both tree. 
    /// In best case it will detect as early possible without memory usage.
    /// Author: Pramod Kumar Chandoria
    /// </summary>
    public class Node
    {
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }

        public Node left;
        public Node right;
        public int data;
    }
    public class SimilarInorderTree
    {
        public static void Main(string[] args)
        {
            var areSame = SimilarInorderTree.TreeWithSameInorder(null, null);
            Console.WriteLine("Null tree expected same, actual result is:" + areSame);

            Node tree1 = new Node(5);
            Node tree2 = new Node(5);
            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with only 1 same node are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(1);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with same Inorder, but not same structure are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(6);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree NOT same Inorder, are expected NOT same, actual result is:" + areSame);

    
        }

        //
        public static bool TreeWithSameInorder(Node tree1, Node tree2)
        {
            IList<int> inOrder1 = new List<int>();
            IList<int> inOrder2 = new List<int>();
            return SameInorder(tree1, tree2, inOrder1, inOrder2) && inOrder1.Count == inOrder2.Count;
        }

        internal static bool SameInorder(Node tree1, Node tree2, IList<int> inOrder1, IList<int> inOrder2)
        {
            
            int topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
            
            if (tree1 == null && tree2 == null)
            {
               return topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            }

            bool isMinTopSame = false;
            if (tree1 != null && tree2 != null)
            {
                if (!SameInorder(tree1.left, tree2.left, inOrder1, inOrder2))
                {
                    return false;
                }

                //topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);

                //isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                //if(!isMinTopSame)
                //{
                //    return false;
                //}

                inOrder1.Add(tree1.data);
                inOrder2.Add(tree2.data);
                topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
                //topIndex++;
                isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                if (!isMinTopSame)
                {
                    return false;
                }

                return SameInorder(tree1.right, tree2.right, inOrder1, inOrder2);
            }

            // One tree is null;
            isMinTopSame = tree1 != null ? SameInorder(tree1.left, null, inOrder1, inOrder2) : SameInorder(null, tree2.left, inOrder1, inOrder2);
                
            if (!isMinTopSame)
            {
                return false;
            }
                
            if (tree1 != null) 
            {
                inOrder1.Add(tree1.data);
            } 
            else 
            {
                inOrder2.Add(tree2.data);
            }

            topIndex = Math.Min(inOrder1.Count -1, inOrder2.Count -1);
            isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            if (!isMinTopSame)
            {
                return false;
            }

            return (tree1 != null ? SameInorder(tree1.right, null, inOrder1, inOrder2) : SameInorder(null, tree2.right, inOrder1, inOrder2));
        }

    }
}

- pc May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean inordertest(Node node1, Node node2){
        Bool flag=new Bool(true);
        inordertest(node1, node2, flag);
        return flag.val;
    }
   
    private static void inordertest(Node node1, Node node2, Bool flag){
   	if(node1==null && node2==null){
	    return;
	}
	if(node1==null || node2 == null){
	    flag.val=false;
	    return;
	}
	inordertest(node1.leftChild, node2.leftChild, flag);
	if(node1.data != node2.data){
	    flag.val=false;
		return;
	}
	inordertest(node1.rightChild, node2.rightChild, flag);
} 

    public static class Bool{
         boolean val;
         public Bool(boolean val){
             this.val=val;
         }
     }

- infinity May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct _node {
	int val;
	struct _node *ln;
	struct _node *rn;
}Node;

int
_isinordersame(Node *t1, Node *t2)
{
	Node *stack1[1000]={NULL};
	Node *stack2[1000]={NULL};
	int top1=-1, prev1=-1;
	int top2=-1, prev2=-1;
	int s1[1000]={-1}, s2[1000]={-1}, last1=-1, last2=-1;
	int same = 1;

	while(t1 || t2) {
		if(t1) {
			if (prev1!=t1->val && t1->ln) {
				stack1[++top1] = t1;
				t1 = t1->ln;
			} else {
				s1[++last1] = t1->val;
				if (t1->rn) t1 = t1->rn;
				else if (top1>=0) {
					t1 = stack1[top1--];
					prev1 = t1->val;
				}
				else t1 = NULL;
			}
		}
		if(t2) {
			if (prev2!=t2->val && t2->ln) {
				stack2[++top2] = t2;
				t2 = t2->ln;
			} else {
				s2[++last2] = t2->val;
				if (t2->rn) t2 = t2->rn;
				else if (top2>=0) {
					t2 = stack2[top2--];
					prev2 = t2->val;
				}
				else t2 = NULL;
			}
		}

		if (last1>=0 && last2>=0) {
			int min = (last1>last2)?last2:last1;
			while(min>=0) {
				if(s1[min]!=s2[min]) {
					same = 0;
					break;
				}
				min--;
			}
			min = (last1>last2)?last2:last1;
			if(last1-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last1-min);i++) s1[i] = s1[k];
			}
			if(last2-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last2-min);i++) s2[i] = s2[k];
			}
			last1 -= min+1;
			last2 -= min+1;
		}
	}
	return same;
}

- Ankzz May 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct _node {
	int val;
	struct _node *ln;
	struct _node *rn;
	struct _node *pn;
}Node;
int
_isinordersame(Node *t1, Node *t2)
{
	Node *stack1[1000]={NULL};
	Node *stack2[1000]={NULL};
	int top1=-1, prev1=-1;
	int top2=-1, prev2=-1;
	int s1[1000]={-1}, s2[1000]={-1}, last1=-1, last2=-1;
	int same = 1;

	while(t1 || t2) {
		if(t1) {
			if (prev1!=t1->val && t1->ln) {
				stack1[++top1] = t1;
				t1 = t1->ln;
			} else {
				s1[++last1] = t1->val;
				if (t1->rn) t1 = t1->rn;
				else if (top1>=0) {
					t1 = stack1[top1--];
					prev1 = t1->val;
				}
				else t1 = NULL;
			}
		}
		if(t2) {
			if (prev2!=t2->val && t2->ln) {
				stack2[++top2] = t2;
				t2 = t2->ln;
			} else {
				s2[++last2] = t2->val;
				if (t2->rn) t2 = t2->rn;
				else if (top2>=0) {
					t2 = stack2[top2--];
					prev2 = t2->val;
				}
				else t2 = NULL;
			}
		}

		if (last1>=0 && last2>=0) {
			int min = (last1>last2)?last2:last1;
			while(min>=0) {
				if(s1[min]!=s2[min]) {
					same = 0;
					break;
				}
				min--;
			}
			min = (last1>last2)?last2:last1;
			if(last1-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last1-min);i++) s1[i] = s1[k];
			}
			if(last2-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last2-min);i++) s2[i] = s2[k];
			}
			last1 -= min+1;
			last2 -= min+1;
		}
	}
	return same;
}

- Ankzz May 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is probably the worst possible way of implementing it unless you really wanted to learn the C++ 11 thread synchronization stuff really badly which is why I did it this way.

// Tree_Match.h
#include <istream>
#include <iostream>

#include <mutex>
#include <thread>
#include <functional>     // std::ref
#include <future>         // std::promise, std::future
using namespace std;

#pragma once 


class Matchup
{
public:
	Matchup()
	{
		lock.lock();
		state = START;
		lock.unlock();
		fut = new std::future < bool > ; // these miserable things cannot be reused so we will be continually deleting and replacing them 
		matched = new std::promise < bool > ;
	}//-----------------------------------------------------

	~Matchup()
	{
		delete fut;
		delete matched;
	}//-----------------------------------------------------

	bool ok()
	{
		lock.lock();
		bool out = (state == START);
		lock.unlock();
		return out;
	}//-----------------------------------------------------
	
	bool put(int v)
	{
		lock.lock();

		switch (state)
		{
		case START:
		{
			value = v;
			state = WAITING_FOR_OTHER;
			*fut = matched->get_future();
			lock.unlock();

			bool out = fut->get();

			lock.lock();  // you can not reuse a future or probabaly a promise so we will just delete them and get new ones   
			delete matched;
			delete fut;
			fut = new std::future < bool >;
			matched = new std::promise < bool >;
			lock.unlock();
			
			return out;
		}

		case WAITING_FOR_OTHER:
		{
			bool m = (v == value);
			matched->set_value(m);
			state = m ? START : FAIL;
			lock.unlock();
			return m;
		}
		case FAIL:
			lock.unlock();
			return false;

		case DONE:
			lock.unlock();
			return false;
		}

		return false;
	}//-----------------------------------------------------

	void done()
	{
		lock.lock();

		if (WAITING_FOR_OTHER == state)
		{
			matched->set_value(false);
			state = FAIL;
		}
		else
		{
			state = DONE;
		}

		lock.unlock();
	}//-----------------------------------------------------


private:

	std::mutex lock;

	enum State { START, WAITING_FOR_OTHER, FAIL, DONE };
	//std::thread::id owner;
	State state;
	int value;
	std::promise<bool> *matched;
	std::future<bool> *fut;
};


class Node
{
public:
	Node()
	{
		left = nullptr;
		right = nullptr;
		data = 0;
	}//----------------------------------------------------------------------
	
	Node(Node *l, int i, Node *r = nullptr)
	{
		left = l;
		right = r;
		data = i;
	}//----------------------------------------------------------------------

	Node(int i, Node *r = nullptr)
	{
		left = nullptr;
		right = r;
		data = i;
	}//----------------------------------------------------------------------
	
	~Node()
	{
		if (left != nullptr)
		{
			delete left;
		}

		if (right != nullptr)
		{
			delete right;
		}
	}//----------------------------------------------------------------------

	void inorder_dump()const
	{
		if (left != nullptr)
		{
			left->inorder_dump();
		}

		cout << data << " ";

		if (right != nullptr)
		{
			right->inorder_dump();
		}
	}//----------------------------------------------------------------------
	
	Node *left;
	Node *right;
	int data;
};

other file 

#include "stdafx.h"
#include <string>
#include <thread>
#include <mutex>
#include <istream>
#include <iostream>
using namespace std;
#include "Tree_Match.h"

std::mutex print_lock;




void tree_comp_thread_r(Node *r, Matchup *match)
{
	if (r->left != nullptr)
	{
		tree_comp_thread_r(r->left, match);
	}

	print_lock.lock();

	cout << std::this_thread::get_id() << " " << r->data << "\n";

	print_lock.unlock();



	bool m = match->put(r->data);

	if (!m)
	{
		return;
	}

	print_lock.lock();

	cout << std::this_thread::get_id() << " " << r->data << " " << m << "\n";

	print_lock.unlock();

	if (r->right != nullptr)
	{
		tree_comp_thread_r(r->right, match);
	}
}


void tree_comp_thread(Node *r, Matchup *match)
{
	tree_comp_thread_r(r, match); // we wrap this to deal with the case when the trees are of differing size
	match->done();
}


int _tmain(int argc, _TCHAR* argv[])
{

	//Node *a = new Node(new Node(new Node(1), 2), 3, new Node(new Node(new Node(4),5), 6));
		         

	//Node *b = new Node(1, new Node(2, new Node(new Node(3), 4, new Node(new Node(5), 6))));

	Node *a = new Node(new Node(1), 2);
	Node *b = new Node(1);


	a->inorder_dump();
	cout << "\n";
	b->inorder_dump();
	cout << "\n";

	Matchup match;

	thread ta = thread(tree_comp_thread, a, &match);
	thread tb = thread(tree_comp_thread, b, &match);

	ta.join();
	tb.join();


	if (match.ok())
	{
		cout << "thay matched\n";
	}
	else
	{
		cout << "thay did not match\n";
	}


}

- Anonymous June 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

notes on the earlier code

I could not find a release and sleep function in the C++ 11 libraries. Instead I found this thing where you have objects called promises and futures. You can use a 'promise' object to create a 'future' object.
fut = prom.get_future()
If you try to get the value out of the future object it will block until you push a value into the promise object
val = fut.get(); // if the promise has not had a value pushed into it at this point the current thread will sleep here until some other thread pushes a value into the promise object
in the other thread you call this:
prom.set_value(m);
wakes up the sleeping thread and the value from m is not put into val
unfortunately it looks like you cannot reuse these things.
So I cannot do this a second time. I may be missing something. So I ended up using pointers and deleting and reallocating new objects every time around. Probably this will have some pretty hefty overhead.
Never the lass this mechanism in general seems like it might have some really interesting uses.
A'

- Dr A.D.M. June 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An implementation to compare objects without using stack

static boolean checkInOrder(Node root1, Node root2) {
		
		InOrderIterator ita1 = new InOrderIterator(root1);
		InOrderIterator ita2 = new InOrderIterator(root2);
		
		while(ita1.hasNext() || ita2.hasNext()){
			Node node1 = ita1.next();
			Node node2 = ita2.next();
			
			if(node1 == null || node2 == null) {
				return false;
			}
		
			if(node1.value != node2.value)
				return false;
		}
		return true;
	}


	static class InOrderIterator {
		Node root;
		
		InOrderIterator(Node root){
			this.root = root;
		}
		
		boolean hasNext() {
			return root != null?true:false;
		}
		
		Node next() {
			Node next = null;
			while(root != null) {
				if(root.left == null){
					next = root;
					root = root.right;
					break;
				} else {
					Node temp = root.left;
					while(temp.right != null && temp.right != root) {
						temp = temp.right;
					}
					if(temp.right == null) {
						temp.right = root;
						root = root.left;
					} else {
						next = temp.right;
						temp.right = null;
						root = root.right;
						break;
					}
				}
			}
			return next;
			
		}
	}

- Killbill June 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSameInorder(Node root1,Node root2)
{
Stack<Node> stk1 = new Stack<Node>();
Stack<Node> stk2 = new Stack<Node>();

boolean ret = true;
boolean comparing = true;

stk1.push(root1.left);
stk1.push(root2.left);

while(comparing)
{

while(root1.left!=null){
stk1.push(root1.left);
root1 = root1.left;
}

while(root2.left!=null){
stk1.push(root2.left);
root2 = root2.left;
}

while(true)
{
Node n1 = stk1.pop();
Node n2 = stk2.pop();

if(n1.data!=n2.data)
{
ret = false;
comparing = false;
break;
}
else if(n1.right!=null && n2.right!=null)
{
stk1.push(n1.right);
stk2.push(n2.right);

root1= n1.right;
root2= n2.right;
break;
}else
{
continue;
}
}

}
return ret;
}

- Abhay June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isSameInorder(Node root1,Node root2)
{
	Stack<Node> stk1 = new Stack<Node>();
	Stack<Node> stk2 = new Stack<Node>();
	
	boolean ret = true;
	boolean comparing = true;
	
	stk1.push(root1.left);
	stk1.push(root2.left);
	
	while(comparing)
	{
	
		while(root1.left!=null){
			stk1.push(root1.left);
			root1 = root1.left;
		}
			
		while(root2.left!=null){
			stk1.push(root2.left);
			root2 = root2.left;
		}
	
	while(true)
	{
		Node n1 = stk1.pop();
		Node n2 = stk2.pop();
		
		if(n1.data!=n2.data)
		{
			ret = false;
			comparing = false;
			break;
		}
		else if(n1.right!=null && n2.right!=null)
		{
			stk1.push(n1.right);
			stk2.push(n2.right);

			root1= n1.right;
			root2= n2.right;
			break;
		}else
		{
			continue;
		}
	}
	
	}
	return ret;
}

- Abhay June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isSameInOrder(Tree t1, Tree t2){

		boolean isTrue=false;
		
		if(t1.value==t2.value){
			isTrue=true;

			if(t1.leftTree!=null && t2.leftTree!=null ){

				isTrue = isSameInOrder(t1.leftTree,t2.leftTree);
			
			}

			if(t1.rightTree!=null && t2.rightTree!=null ){
				
				isTrue = isSameInOrder(t1.rightTree,t2.rightTree);
			
			}

		}
		else{
			isTrue=false;
		}

		return isTrue;

	}

- snehit.gajjar June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a stack to do an in-order traversal of both trees. Usual single-tree In-order traversals add on left child until it's NULL, then visit the parent, then recurse right. This algorithm recurses left down the first tree until it finds the NULL child, then pauses as the parent so that it can then do the same with the second tree. One this next "in-order" Node is found, the two are compared. If they are different, we return false. If they are the same, we keep going, recursing right.

struct Node {
	Node* left;
	Node* right;
	char data;
};

bool treesHaveSameInorder(Node* root1, Node* root2) {
    if( (!root1 && root2) || (root1 && !root2) ) return false;
    if(root1 && root2) return true;
    stack<Node*> s1, s2;
    s1.push(root1);
    s2.push(root2);
    Node* trav1 = root1->left;
    Node* trav2 = root2->left;
    while(!s1.empty() && !s2.empty()) {
        while(trav1) {
            s1.push(trav1);
            trav1 = trav1->left;
        }
        trav1 = s1.top();
        s1.pop();
        while(trav2) {
            s2.push(trav2);
            trav2 = trav2->left;
        }
        trav2 = s2.top();
        s2.pop();
        if(trav1->data != trav2->data) return false;
        trav1 = trav1->right;
        trav2 = trav2->right;
    }
    if(!s1.empty() || !s2.empty()) return false;
    return true;
}

- Josh August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a class BSTInOrderIterator

class BSTInOrderIterator {
BSTNode root;
Stack<BSTNode> s;
public BSTInOrderIterator(BSTNode root) {}
boolean hasNext();
BSTNode next();
}
just implement the inorder traversal in iterator.

Then you can initializes two instance and compare.

- sakar2003 December 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my java code :

class Nodecomp{
	Nodecomp left, right;
	int data;
	Nodecomp(int x){
		data=x;
	}
}
public class CompareInorder {

	Nodecomp root;
	boolean InOrder(Nodecomp node1, Nodecomp node2){
		Stack<Nodecomp> stack=new Stack<Nodecomp>();
		Stack<Nodecomp> stack2=new Stack<Nodecomp>();
		Nodecomp n=node1;
		Nodecomp n2=node2;
		if(n==null||n2==null)
			return false;
		while(n!=null){
			stack.push(n);
			n=n.left;
		}
		while(n2!=null){
			stack2.push(n2);
			n2=n2.left;
		}
		
		while(stack.size()>0&&stack2.size()>0){
			n=stack.pop();
			n2=stack2.pop();
			if(n.data!=n2.data){
				return false;
			}
			if(n.right!=null){
				n=n.right;
				while(n!=null){
					stack.add(n);
					n=n.left;
					
				}
			}
			if(n2.right!=null){
				n2=n2.right;
				while(n2!=null){
					stack2.add(n2);
					n2=n2.left;
					
				}
			}
		}
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CompareInorder tree=new CompareInorder();
		tree.root=new Nodecomp(1);
		tree.root.left=new Nodecomp(2);
		tree.root.right=new Nodecomp(3);
		CompareInorder tree1=new CompareInorder();
		
		tree1.root=new Nodecomp(2);
		tree1.root.right=new Nodecomp(1);
		tree1.root.right.right=new Nodecomp(3);
		System.out.println("Are they equal :"+tree1.InOrder(tree.root, tree1.root));
	}

}

- RishabG June 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static boolean testInOrderStack(TreeNode tree1, TreeNode tree2) throws Exception {
		Stack<TreeNode> stack1 = new Stack<TreeNode>(5);
		Stack<TreeNode> stack2 = new Stack<TreeNode>(5);
		Stack<TreeNode> result = new Stack<TreeNode>(5);
		// push root
		stack1.push(tree1);
		stack2.push(tree2);
		// hash set to mark roots that are visited
		Set<TreeNode> set1 = new HashSet<TreeNode>();
		Set<TreeNode> set2 = new HashSet<TreeNode>();
		while (!stack1.isEmpty() && !stack2.isEmpty()) {
			/* wait until the first push to the result stack that
			 * stores the in order traversal of the first tree.
			 */
			boolean waitTree1 = true;
			while(waitTree1) {
				TreeNode root1 = stack1.pop();
				// if already visited root or a leaf node
				if ((set1.contains(root1)) || (root1.left == null && root1.right == null)) {
					result.push(root1);
					waitTree1 = false;
				} else {
					// put left child
					if (root1.left != null) {
						stack1.push(root1.left);
					}
					// put root
					stack1.push(root1);
					set1.add(root1);// mark root as visited
					// put right
					if (root1.right != null) {
						stack1.push(root1.right);
					}
				}
			}
			
			boolean waitTree2 = true;
			while(waitTree2) {
				// repeat for tree2
				TreeNode root2 = stack2.pop();
				// if already visited root or a leaf node
				if ((set2.contains(root2)) || (root2.left == null && root2.right == null)) {
					// match with result
					if (result.peek().data != root2.data) {
						System.out.println("They ain't matching!");
						return false;
					}
					waitTree2 = false;
				} else {
					// get left child
					if (root2.left != null) {
						stack2.push(root2.left);
					}
					stack2.push(root2);
					set2.add(root2);// mark root as visited
					if (root2.right != null) {
						stack2.push(root2.right);
					}
				}
			}
		}
		return true;
	}

// Test Code:

public static void testInOrderParallel() throws Exception {
//		smaller tree example...
//		TreeNode tree1 = new TreeNode(5);
//		tree1.left = new TreeNode(3);
//		tree1.right = new TreeNode(7);
//
//		TreeNode tree2 = new TreeNode(3);
//		tree2.right = new TreeNode(5);
//		tree2.right.right = new TreeNode(7);
//		Complex tree example...
		TreeNode tree1 = new TreeNode(6);
		tree1.left = new TreeNode(4);
		tree1.left.right = new TreeNode(5);
		tree1.right = new TreeNode(8);
		tree1.right.left = new TreeNode(7);
		
		TreeNode tree2 = new TreeNode(7);
		tree2.left = new TreeNode(5);
		tree2.left.left = new TreeNode(4);
		tree2.left.right = new TreeNode(6);
		tree2.right = new TreeNode(8);
		
		System.out.println(testInOrderStack(tree1, tree2));

	}

- code.runner October 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You could always do the in-order of one, flattening to, say, an array, then do the other, comparing with the in-order of the first. However this ends up reading an entire tree when they may differ right from the first node. So the better approach is to read the in-order of both at the same time and short-circuit out when you detect a difference.In-order traversal of trees can be done iteratively using stacks. A recursive solution is also possible and easier to code.

// Helper to push left most node rooted at n to stack
void pushLeftMostNode(Node n, Stack<Node> s) {
     while (n != null && n.left != null) {
        n = n.left;
        s.push(n);
    }
}

// Helper to push in-order next node rooted at n to stack
void pushInOrderNextNode(Node n, Stack<Node> s) {
    if (n.left != null) {
        pushLeftMostNode(n, s);
    } else if (n.right != null) {
        s.push(n.right);
        pushLeftMostNode(n.right, s);
    }
}

boolean isSame(Node n1, Node n2) {

    // Use stacks to iterate over trees in-order
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();

    // While stacks contain nodes, tops of stack will be the in-order next node
    while (!s1.isEmpty() && !s2.isEmpty() {
        n1 = s1.pop();
        n2 = s2.pop();
        if (n1.val != n2.val) {
            return false; // Short-circuit out
        }
        // Push in-order next nodes for trees rooted at n1 and n2
        pushInOrderNextNode(n1, s1);
        pushInOrderNextNode(n2, s2);
    }

    // If either stack contains nodes at this point, then trees are different sizes
    // Otherwise, trees are the same size and in-order traversals are the same too
    return !s1.isEmpty() || !s2.isEmpty();
}

- JW April 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to push in-order next of n1, n2 after initialization of s1 and s2.

- JW April 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in the example above both Trees differ right from the root, and still they give the same inorder output, so correct me if I'm wrong but your solution fails on that case, a much simpler solution would be to output both inOrder traversals as a string and compare them.

- guilhebl April 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will be correct if you push both roots and then add the leftmost nodes for the roots before the while loop. This will properly initialize the condition that the first element in both stacks is the left most element of each tree.

- Anonymous April 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think there are more problems. Firstly pushLeftMostNode will be in cycle if node has a left son (you call it with the same parameters). Then, you never dismiss the processed nodes from the tree, therefore you will stay on the most left branch for all the time. Or do I miss something? Otherwise, I think it should be OK

- Demo April 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If a 2 trees have the same in-order, then 1 tree will have the reverse postorder of the other's inorder. You can use a stack to push values for one tree. Then do a post order of 2nd tree, and keep popping till you don't see a match.

- legolas April 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The problem becomes easy if you have an in-order tree iterator and this solution doesn't require you to traverse all the nodes of the tree.

- Anonymous April 28, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More