Same Tree

Share

Determine if two binary trees are identical (same structure and values).

Example 1
Input: p=[1,2,3], q=[1,2,3] → Output: true
Example 2
Input: p=[1,2], q=[1,null,2] → Output: false

Solution Approach

Recursive DFS: compare root values, then recursively check left and right subtrees.

  • If both null return true
  • If one null or values differ return false
  • Recursively check left and right subtrees
Java
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
  • Time Complexity: O(n)
  • Space Complexity: O(h)