Same Tree
You get the roots of two binary trees, p and q. Return true if they are the same tree: the same shape, with the same value at every position. Otherwise return false.
Two empty trees are the same. The trees are written in level order, with null for a missing child.
Examples
Input p = [1, 2, 3], q = [1, 2, 3]
Output true
Input p = [1, 2], q = [1, null, 2]
Output false
The same values, but 2 is a left child in one tree and a right child in the other.
Input p = [1, 2, 1], q = [1, 1, 2]
Output false
The same shape, but the values differ.
Constraints
- 0 <= number of nodes in each tree <= 100
- -10,000 <= node value <= 10,000
Stuck? Take one hint at a time
Common mistakes
- Comparing only the values and ignoring the shape, so [1, 2] and [1, null, 2] look the same.
- Calling .val on an empty node because the empty cases were not handled before the value comparison.
- Returning true when exactly one node is empty.
- Stopping after the left subtrees and never comparing the right ones.
Questions an interviewer may ask next
- Check whether one tree is a subtree of another. (Subtree of Another Tree: Same Tree at every node.)
- Check whether a tree is symmetric. (Compare the left subtree with the mirror of the right.)
- Compare two trees without recursion and without a stack, in O(1) extra memory. (A Morris traversal.)
- Compare two binary search trees that hold the same values but may have different shapes. (Compare their in order sequences.)
p
[1,2,3]
q
[1,2,3]
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.