LeetCode 100 · Trees

Same Tree, explained with a picture

Two gardeners comparing their trees.

EasyTrees
▶ Watch it step by step

The problem

Given two binary trees, decide whether they are exactly the same: same shape and same values in the same places.

Input:  [1, 2, 3, 4, 5] and [1, 2, 3, 4, 6]
Output: false   (5 ≠ 6)

Picture it

Picture two gardeners each standing at the top of their own tree. They walk down both trees in lockstep, always taking the same turn. At each spot they compare: both empty is fine; one empty and one not, or different values, means the trees differ.

How to recognise it

  • You get two binary trees and a yes/no question about both at once.
  • "Same" means same shape and same values in the same places, so you compare position by position.
  • The answer for two roots depends on the answers for their left pair and their right pair: a recursive, depth-first search (DFS: follow one branch to the bottom before trying the next) over two trees in step.
  • Up to 100 nodes each, so any O(n) approach is fine. What matters is getting the empty-node cases right.

Start with brute force

Write each tree out as text, including a marker for every empty spot, and compare the two strings.

def ser(node):
    out = []
    def walk(n):
        if not n:
            out.append("#")
            return
        out.append(str(n.val))
        walk(n.left)
        walk(n.right)
    walk(node)
    return ",".join(out)

def is_same_brute(p, q):
    return ser(p) == ser(q)

This is correct and already O(n + m) time, but it builds two full strings, O(n + m) extra memory, and it always reads both whole trees even when the roots differ. The # markers are essential: without them, [1, 2] and [1, null, 2] both write out as 1,2.

From brute force to the idea

  1. Find the waste. The strings are compared one token at a time anyway, so we can compare the trees directly, without writing anything down.
  2. Settle the empty cases first. Both empty: same. Exactly one empty: different. That replaces the # markers.
  3. Compare the values. If both nodes exist but p.val != q.val, the trees differ.
  4. Recurse in step. Compare the two left children together and the two right children together. and stops at the first False, so a difference near the top ends the search early.

This is the key idea: walk both trees together, and two spots match when both are empty, or both hold the same value and their children match.

The key idea

Recursive lockstep walk: same(p, q) = values equal and same(left, left) and same(right, right). O(n).

Python solution

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

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (serialise both)O(n + m): every node written onceO(n + m): the two strings
Paired DFS (shown code)O(min(n, m)): it stops at the first difference or when the smaller tree runs outO(min(h1, h2)): one stack frame per level of the shared path

Edge cases

  • Both empty: True.
  • One empty, one not: False.
  • Same values, different shape ([1, 2] and [1, null, 2]): False; at the root's left, one side is empty.
  • Same shape, one different value ([1, 2, 3, 4, 5] and [1, 2, 3, 4, 6]): False.
  • Mirror images ([1, 2, 3] and [1, 3, 2]): False; mirrored is not the same.
  • Deep trees: LeetCode allows only 100 nodes, so the recursion limit (about 1,000 levels) is not a concern here.

Common mistakes

  • Comparing values before checking for None, which raises AttributeError when one side is empty.
  • Comparing traversals without empty markers, which treats different shapes as equal.
  • Comparing left with right (that tests mirror images, not sameness).
  • Writing p == q for nodes: that compares object identity, not contents.
Your turn: equal after flips

Two trees are flip equivalent (LeetCode 951) if you can make them the same by swapping the left and right children of any number of nodes. Decide whether two trees are flip equivalent. Describe your approach, then write it if you like.

Compare with our answer

Same paired walk, but at each pair of nodes allow two matchings: children in the same order, or crossed over.

def flip_equiv(p, q):
    if not p or not q:
        return p is q                      # both empty?
    if p.val != q.val:
        return False
    return ((flip_equiv(p.left, q.left) and flip_equiv(p.right, q.right)) or
            (flip_equiv(p.left, q.right) and flip_equiv(p.right, q.left)))

With unique values (as LeetCode guarantees) only one matching can succeed at the root of each pair, so this stays fast in practice; with many repeated values the two tries can multiply. A safe alternative is to give each subtree a canonical form, with its two children written in a fixed order (for example, by comparing their canonical strings), and compare the two forms.

A strong answer mentions: the both-empty case, trying both pairings at each node, and why repeated values can make the plain version slower.

Check what stuck

1. You must check whether two folder trees on disk are identical, including the order of subfolders. Which approach fits best?

2. Why can the shown solution stop before reading both trees?

3. A learner compares the trees by their preorder value lists with no markers for empty spots. Which pair of different trees is wrongly judged the same?

Score 60% or more and the lesson is marked complete.