100. Same Tree

Given two binary trees, write a function to check if they are equal or not. 

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Below are some examples:

Ex. 1:
Tree 1:
                   10
        20                   30
  40        50        60        70

Tree 2:    
                  10
        20                   30
  40        50        60        70
Tree 1 & Tree 2 are identical.

Example 2:
Tree 1:    
                 10
        20                   30
  40        50        60        70
Tree 2:
                   10
        20                   30
  40        60        50        70

Trees 1 & 2 are not identical as their structures are same but values at nodes 50 and 60 differ.

Example 3:
Tree 1:
                   10
        20                   30
  40        50        60        
Tree 2:
                   10
        20                   30
  40        50                  60

Trees 1 & 2 are not identical as the structures are not same as 60 is on left subtree of node 30 in Tree 1 but on right subtree of node 30 in Tree 2.

Approach : Use the simple recursive solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL){ return true; } if(p == NULL && q != NULL || p != NULL && q == NULL){ return false; } if(p->val == q->val){ return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } return false; }