On this page

Same Tree

Given the roots of two binary trees p and q, check whether they are the same: they must be structurally identical and every pair of corresponding nodes must have the same value.

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

Intuition

Two trees are the same when their roots match and their left subtrees are the same and their right subtrees are the same. That is a recursive definition, so the code mirrors it.

The base cases decide everything:

  • Both nodes null: they match, return true.
  • Exactly one is null: the shapes differ, return false.
  • Both exist but values differ: return false.

Approach: Walk Both Trees Together

  1. If both are null, return true.
  2. If either is null (only one, since both-null was handled), return false.
  3. If p.val != q.val, return false.
  4. Return isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

The && short-circuits, so the walk stops at the first mismatch. Any traversal order works here, as long as both trees are walked in the same order.

Code

class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};

Complexity

Time: O(min(n, m))

We stop as soon as one tree runs out or a mismatch is found. In the worst case, identical trees, every node is visited once.

Space: O(h)

Recursion stack depth equals the height of the smaller tree being compared.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Two trees are the same if their roots match and both their left subtrees and right subtrees are the same, so I recurse on both trees at once. If both nodes are null I return true. If only one is null the shapes differ, so I return false. If the values differ I return false. Otherwise I return the AND of the left comparison and the right comparison, which short-circuits on the first mismatch. Time is O of the smaller tree size and space is O of the height."
Next TopicBinary Tree Zigzag Level Order Traversal