Friday, April 4, 2014

Check if two binary trees are identical

Given two binary tress, how do we check if they are identical in structure, and  contents?

For example the following two binary trees are identical.
We can solve this problem using recursion effectively. The function checks if the root element is equal and use the same function to check if it's left and right sub-trees are also identical. If it is we return true. 

Here is the C++ function.


bool isSameTree(TreeNode *p, TreeNode *q) {
        if( p && q )
        {
            if( p->val != q->val )
                return false;
            
            return ( isSameTree(p->left,q->left) && isSameTree(p->right,q->right) );
        }
        else if( !p && !q)
            return true;
        else
            return false;
    }