Same Tree

Easy Trees & BST Recursion Original on LeetCode

Same Tree is a easy trees & bst problem solved with the recursion pattern. The best approach, recursive, runs in O(n) time and O(h) space. Below are 2 approaches in Java, from iterative (queue of pairs) up.

Problem

Given the roots of two binary trees, decide whether they are identical: same shape and same values in every position.

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
Why: Same values, different shape.

Constraints

Each tree has 0 to 100 nodes.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Iterative (queue of pairs)	`O(n)`	`O(n)`
Recursive	`O(n)`	`O(h)`

1Iterative (queue of pairs)

TimeO(n)

SpaceO(n)

Compare nodes pairwise with a queue.

Queue (p, q). Poll a pair; both null → continue; one null or values differ → false.
Add (left, left) and (right, right).

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Deque<TreeNode[]> dq = new ArrayDeque<>();
        dq.add(new TreeNode[] { p, q });
        while (!dq.isEmpty()) {
            TreeNode[] pair = dq.poll();
            TreeNode a = pair[0], b = pair[1];
            if (a == null && b == null) continue;
            if (a == null || b == null || a.val != b.val) return false;
            dq.add(new TreeNode[] { a.left, b.left });
            dq.add(new TreeNode[] { a.right, b.right });
        }
        return true;
    }
}

2Recursive

TimeO(n)

SpaceO(h)

Both null: equal. Exactly one null or different values: not equal. Otherwise compare both left subtrees and both right subtrees.

if p == null || q == null return p == q.
return p.val == q.val && same(p.left, q.left) && same(p.right, q.right).

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Edge cases to test

Both empty (true)
One empty, one not

Hints

Hint 1

Two trees are equal if the roots match and both pairs of subtrees are equal.

FAQ

What is the best time complexity for Same Tree?

Recursive runs in O(n) time and O(h) extra space.

Which pattern does Same Tree use?

It is a trees & bst problem that uses the recursion pattern. Other problems with the same pattern: Binary Tree Inorder Traversal (Recursive), Binary Tree Preorder Traversal (Recursive), Binary Tree Postorder Traversal (Recursive).

Is there a brute force solution for Same Tree?

Yes. Iterative (queue of pairs) takes O(n) time and O(n) space. Compare nodes pairwise with a queue.

Which edge cases should I test for Same Tree?

Both empty (true); One empty, one not.