19. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

Solution: (Comparing node by node with equal root)

class Solution
{
public:
    bool compare(TreeNode *head1, TreeNode *head2)
    {
        queue<TreeNode *> q1;
        queue<TreeNode *> q2;

        q1.push(head1);
        q2.push(head2);

        while (!q1.empty() && !q2.empty())
        {

            TreeNode *p = q1.front();
            q1.pop();

            TreeNode *q = q2.front();
            q2.pop();

            if (p->val != q->val)
            {
                return false;
            }

            if (p->left && !q->left || q->left && !p->left)
            {
                return false;
            }

            if (p->right && !q->right || q->right && !p->right)
            {
                return false;
            }

            if (p->left)
            {
                q1.push(p->left);
                q2.push(q->left);
            }

            if (p->right)
            {
                q1.push(p->right);
                q2.push(q->right);
            }
        }

        return true;
    }

    bool isSubtree(TreeNode *s, TreeNode *t)
    {

        stack<TreeNode *> st;

        while (!st.empty() || s != NULL)
        {
            if (s != NULL)
            {
                if (s->val == t->val)
                {
                    if (compare(s, t))
                    {
                        return true;
                    }
                }
                st.push(s);
                s = s->left;
            }
            else
            {
                s = st.top();
                st.pop();
                s = s->right;
            }
        }

        return false;
    }
};

Time Complexity: O(N M) (n = nodes in s, m = nodes in t)