EasyDepth-First SearchBreadth-First SearchTreeUpdated Sep 2026

100. Same Tree

Asked at Google, Meta, Amazon, Microsoft and 2 more

Difficulty

Easy

Time

O(n)

Space

O(h)

Pattern

Depth-First Search

Companies

6

Problem

You are given the roots of two binary trees, p and q. Decide whether the two trees are the same.

Two trees count as the same only when they match in two ways at once: the shape is identical (every node sits in the same position, including missing children) and every matching pair of nodes holds the same value.

Return true if the trees are identical, otherwise false. Both trees may be empty — two empty trees are the same.

Same shape AND same values

21p3Tree p: root 1, left 2, right 3.21q3Tree q looks exactly the same, so the answer is true.
Every position must line up: root with root, left with left, right with right, and the values must match.

Constraints

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

Examples

Example 1
Inputp = [1,2,3], q = [1,2,3]
Outputtrue
WhyBoth trees have root 1, left child 2 and right child 3. Same shape, same values everywhere, so they match.
Example 2
Inputp = [1,2], q = [1,null,2]
Outputfalse
WhyIn p the 2 is the left child of 1. In q the left child is missing and the 2 is the right child. The values are the same but the positions differ, so the shapes are not identical.
Example 3
Inputp = [1,2,1], q = [1,1,2]
Outputfalse
WhyThe shapes match, but the left children are 2 and 1, and the right children are 1 and 2. The values at those positions differ, so the trees are not the same.

Asked At

6 companies
CompanyDifficulty
GoogleEasyView all Google questions →
MetaEasyView all Meta questions →
AmazonEasyView all Amazon questions →
MicrosoftEasyView all Microsoft questions →
AppleEasyView all Apple questions →
UberEasyView all Uber questions →

How to Think About It

1

Recursive: both null → same. One null, one not → different. Values differ → different. Otherwise, recurse on left children and right children.

2

The three checks in order: (1) are both nodes null? (2) is one null and the other not? (3) do values differ? If none of these, recurse.

3

BFS alternative: use two queues, push roots of both trees. Process both queues simultaneously. Compare values and children positions.

4

Edge cases: both null (true), one null (false), different structures (false), same structure different values (false).

Optimal Approach

Recursive DFS:
Step 1: If both p and q are null → return true.
Step 2: If one is null and the other isn't → return false.
Step 3: If values differ → return false.
Step 4: Recurse: sameTree(p.left, q.left) AND sameTree(p.right, q.right).

The order matters: check null first (base case), then values, then recurse.

Time: O(n) — visit every node once. Space: O(h) — recursion stack.

Compare node pairs top-down

211 == 1, recurse3Roots both hold 1, so move on to the children.22 == 2133 == 3Left pair 2 and 2 match, right pair 3 and 3 match.both null -> trueone null -> falsevalues differ -> falseelse: left AND right
At each step check both null, then one null, then the values; only then go deeper.
ComplexityTime O(n)Space O(h)Each pair of nodes is compared once, and the recursion stack grows with the height h of the tree.

What Trips People Up in Real Interviews

1

Only checking values, not structure. Two trees can have the same values but different structures. Check both.

2

Forgetting to check if both nodes are null. Two null nodes are considered the same tree.

3

Not handling the case where one node is null and the other isn't. This means the trees are different.

4

Confusing "same tree" with "identical structure." Same tree means both structure AND values must match.

5

Not checking values after confirming both nodes exist. After ruling out null mismatches, you must compare p.val != q.val before recursing — skipping this gives wrong results for same-structure different-value trees.

Solution Code

O(n) time
def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Same Tree problem?

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

How do you solve Same Tree?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Same Tree?

Same Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a easy difficulty problem.

What are common mistakes on Same Tree?
  • Only checking values, not structure. Two trees can have the same values but different structures. Check both.
  • Forgetting to check if both nodes are `null`. Two `null` nodes are considered the same tree.
  • Not handling the case where one node is `null` and the other isn't. This means the trees are different.
  • Confusing "same tree" with "identical structure." Same tree means both structure AND values must match.
  • Not checking values after confirming both nodes exist. After ruling out `null` mismatches, you must compare p.val != q.val before recursing — skipping this gives wrong results for same-structure different-value trees.