mafeshsho8lmafeshsho8l
Get Started
All coding questions

Same Tree

easy
NeetCode 150treesrecursion

Problem

Given the roots of two binary trees, decide whether they are structurally identical and hold the same values at every position. Return true only if both shape and values match.

Examples

Input: [1, 2, 3] and [1, 2, 3]
Output: true
Identical structure and values.
Input: [1, 2] and [1, null, 2]
Output: false
The child sits on different sides.

Constraints

  • • 0 <= number of nodes in each tree <= 100
  • • -10^4 <= node value <= 10^4
Hints(tap to reveal)
  • 1. Compare nodes pairwise.
  • 2. Both must be null or both non-null with equal values.
Optimal approach(spoiler)
  1. If both nodes are null, they match.
  2. If exactly one is null or values differ, they do not match.
  3. Otherwise recurse on the left pair and the right pair.
  4. Both recursive checks must succeed.
  5. O(n) time, O(h) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor