Same Tree

Problem:

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.

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public boolean isSameTree(TreeNode p, TreeNode q) {  
12:      if(p==null&&q==null)  
13:       return true;  
14:      if(p!=null && q!=null)  
15:      {  
16:        if(p.val==q.val)  
17:         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);  
18:        else  
19:        return false;  
20:      }  
21:      else  
22:       return false;  
23:    }  
24:  }  

Discussion:

Use pre-order to traverse the trees.