Skip to main content

100. Same Tree

easy

Decide whether two binary trees are structurally identical with the same values at every position. Pure recursion with three base cases.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Constraints

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Three base cases: both null (equal), one null one not (unequal), both non-null with different values (unequal).

Hint 2

Otherwise recurse on left and right subtrees.

Hint 3

AND-combine: same(p.left, q.left) AND same(p.right, q.right).

Solution approach

Reveal approach

Recursive structural compare. Base cases first: if both p and q are null, return true; if exactly one is null, return false; if p.val != q.val, return false. Otherwise return sameTree(p.left, q.left) AND sameTree(p.right, q.right). Each node is visited at most once per tree, so O(n) time. Recursion stack is O(h) where h is the tree height — up to O(n) for skewed trees.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

More Trees practice problems

See all Trees problems →