Traversing two trees together?

Question

I am looking a lot of interview problems where the question requires traversing two trees together, I am not sure exactly how to go about doing this.

e.g.

Given references to roots of two binary trees, how do you determine whether the sequence of the leaf elements equal but you must implement short circuiting return when the first node violates the rule.

Answer 1

Is your question asking to find out whether: "the sequence created by visiting all the leaf nodes of 2 trees is same"

with a constraint that when found a mismatch of leaf values, then we must quit immediately.

If so, I propose following solution:

insert (root of tree1) in stack1
insert (root of tree2) in stack2

temp1 = (root of tree1) -> left child
temp2 = (root of tree2) -> left child

while(stack1 and stack2 arent empty) 
{
    found = false
    while(found == false) {
        if (temp1 is leaf node)
            child1 = value of temp1
            found = true
            pop element from stack1
            set temp1 to its right child

        if (temp1 has left child)
            put temp1 in stack1
            set temp1 to its left child
    }

    found = false
    while(found == false) {
        if (temp2 is leaf node)
            child2 = value of temp2
            found = true
            pop element from stack2
            set temp2 to its right child

        if (temp2 has left child)
            put temp2 in stack2
            set temp2 to its left child
    }

    if(child1 != child2) 
        return
}

Answer 2

One possible solution:

• I have created a tree class which has a method GetNextLeafNode(). This is responsible for returning the next immediate leaf node of a tree.

• With the tree class I am keeping a stack to maintain the traversed elements

• In the GetNextLeafNode() method, I am doing iterative tree traversal (Pre order).

Whenever I encounter a node(stack.Pop()) which is leaf I am just returning it. Otherwise I am pushing left and right pointers to the stack. Initially root node is pushed. At any time state of stack is proper.

Here is the code in C#:

    public TreeNode GetNextLeafNode()
    {
        TreeNode leaf = null;

        while (s.Count != 0)
        {
            TreeNode n = s.Pop();
            if ((n.Left == null) && (n.Right == null))
            {
                leaf = n;
                return leaf;
            }
            else
            {
                if (n.Right != null)
                    s.Push(n.Right);
                if (n.Left != null)
                    s.Push(n.Left);
            }
        }

        return leaf;
    }

Now, we can create two different trees say, t1 and t2. We can do the comparision as follows:

        int data1 = t1.GetNextLeafNode().Data;
        int data2 = t2.GetNextLeafNode().Data;

        while (data1 == data2)
        {
            //both the leaf nodes are same.
            data1 = t1.GetNextLeafNode().Data;
            data2 = t2.GetNextLeafNode().Data;
        }