Overview

Given the roots of two binary trees, determine if they are structurally identical and have the same node values.

Implement isSameTree(p, q).

Constraints

• Tree nodes have shape { val, left, right }.
• Both trees may be null (two null trees are equal).
• Node values are integers.
• Aim for $O(n)$ time where n is the number of nodes in the smaller tree.

Examples

//   1       1
//  / \\    / \\
// 2   3  2   3
isSameTree(p, q);  // true

//   1       1
//  /         \\
// 2           2
isSameTree(p, q);  // false — different structure

//   1       1
//  / \\    / \\
// 2   1  1   2
isSameTree(p, q);  // false — different values

Notes

• Recursive approach: two trees are equal if their roots have the same value, and their left subtrees are equal, and their right subtrees are equal.
• Base cases: both null → true, one null → false.
• Can also be solved iteratively with a queue (BFS comparison).

Solution

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Resources

• Same Tree — LeetCode
• Tree Traversal — Wikipedia