Algorithm - Stack

http://www.geeksforgeeks.org/find-first-non-matching-leaves-two-binary-trees/

Given two binary trees, find first leaves of two trees that do not match. If there are no non-matching leaves, print nothing.

Method 1 (Simple) : 
Do Inorder traversal of both trees one by one, store the leaves of both trees in two different lists. Finally find first values which are different in both lists. Time complexity is O(n1 + n2) where n1 and n2 are number of nodes in two trees. Auxiliary space requirement is O(n1 + n2).

Method 2 (Efficient)
This solution auxiliary space requirement as O(h1 + h2) where h1 and h2 are heights of trees. We do Iterative Preorder traversal of both the trees simultaneously using stacks. We maintain a stack for each tree. For every tree, keep pushing nodes in the stack till the top node is a leaf node. Compare the two top nodes f both the stack. If they are equal, do further traversal else return.

bool isLeaf(Node * t)

{

    return ((t->left == NULL) && (t->right == NULL));

}

 

// Prints the first non-matching leaf node in

// two trees if it exists, else prints nothing.

void findFirstUnmatch(Node *root1, Node *root2)

{

    // If any of the tree is empty

    if (root1 == NULL || root2 == NULL)

      return;

 

    // Create two stacks for preorder traversals

    stack<Node*> s1, s2;

    s1.push(root1);

    s2.push(root2);

 

    while (!s1.empty() || !s2.empty())

    {

        // If traversal of one tree is over

        // and other tree still has nodes.

        if (s1.empty() || s2.empty() )

           return;

 

        // Do iterative traversal of first tree

        // and find first lead node in it as "temp1"

        Node *temp1 = s1.top();

        s1.pop();

        while (temp1 && !isLeaf(temp1))

        {

            // pushing right childfirst so that

            // left child comes first while popping.

            s1.push(temp1->right);

            s1.push(temp1->left);

            temp1 = s1.top();

            s1.pop();

        }

 

        // Do iterative traversal of second tree

        // and find first lead node in it as "temp2"

        Node * temp2 = s2.top();

        s2.pop();

        while (temp2 && !isLeaf(temp2))

        {

            s2.push(temp2->right);

            s2.push(temp2->left);

            temp2 = s2.top();

            s2.pop();

        }

 

        // If we found leaves in both trees

        if (temp1 != NULL && temp2 != NULL )

        {

            if (temp1->data != temp2->data )

            {

                cout << "First non matching leaves : "

                     << temp1->data <<"  "<< temp2->data

                     << endl;

                return;

            }

        }

    }

}