How do you approach Same Tree?

Compare the two trees at the same index simultaneously, rather than traversing one and then the other.

What is the time complexity of Same Tree?

Time complexity: O(n) where n is the smaller tree.. Space complexity: O(h) for the recursion stack..

What are common mistakes on Same Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Same Tree

EasyData Structures

Description

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.

Example 1

Input: p = [1,2,3], q = [1,2,3]

Output: true

Example 2

Input: p = [1,2], q = [1,null,2]

Output: false

Example 3

Input: p = [1,2,1], q = [1,1,2]

Output: false

Constraints

- 0 <= number of nodes <= 100 - -10^4 <= Node.val <= 10^4

Same Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

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 Treesproblems →

If you are stuck

Show the 3-step hint ladder

Compare the two trees at the same index simultaneously, rather than traversing one and then the other.
At each index: if both are missing, they match; if exactly one is missing, they differ; otherwise compare values and recurse into both children.
Treat an index past the end of the array the same as an explicit null - that is what makes trees of different sizes comparable.

The optimal approach

Show the approach: Walk both trees in lockstep

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.

Time: O(n) where n is the smaller tree.
Space: O(h) for the recursion stack.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

← Back to problems

Same Tree

EasyData Structures

Description

Example 1

Input: p = [1,2,3], q = [1,2,3]

Output: true

Example 2

Input: p = [1,2], q = [1,null,2]

Output: false

Example 3

Input: p = [1,2,1], q = [1,1,2]

Output: false

Constraints

- 0 <= number of nodes <= 100 - -10^4 <= Node.val <= 10^4

Same Tree: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

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 Treesproblems →

If you are stuck

Show the 3-step hint ladder

Compare the two trees at the same index simultaneously, rather than traversing one and then the other.
At each index: if both are missing, they match; if exactly one is missing, they differ; otherwise compare values and recurse into both children.
Treat an index past the end of the array the same as an explicit null - that is what makes trees of different sizes comparable.

The optimal approach

Show the approach: Walk both trees in lockstep

Time: O(n) where n is the smaller tree.
Space: O(h) for the recursion stack.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.