We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding node holds the same value.
The tree is given as a level-order array with explicit nulls, where the children of index i sit at 2i + 1 and 2i + 2. An empty array is an empty tree.
An easy trees problem, graded against 6 test cases (3 of them hidden).
Recursive traversal of binary trees and BSTs - depth, validation, and path problems.
Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.
More Trees problems →The temptation is to serialize each tree and compare the results, but that is more work and gets the null handling wrong in subtle ways. Recurse into both trees at once instead, comparing node by node.
Three cases at each position: both absent (match, return true), exactly one absent (structural difference, return false), or both present (compare values, then recurse into both left children and both right children). The early return on a mismatch means a difference near the root costs almost nothing.
The detail that makes it work on array-encoded trees is treating an out-of-range index identically to an explicit null. Without that, `[1,2]` and `[1,2,null]` would compare unequal despite being the same tree.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.