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
- If both are
null, return true. - If either is
null(only one, since both-null was handled), return false. - If
p.val != q.val, return false. - 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