DSA Same Tree

The problem

Two trees are the same tree when two things hold at once. They have the same shape, and they have the same value at every matching position.

Shape means which child slots are filled, ignoring values. A left child and a right child are different slots. Two trees with the same values in different slots have different shapes.

The input is two roots. The output is one boolean, True for the same tree and False otherwise. Two empty trees are the same tree.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def build(leaf_value):
    return TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(leaf_value)))

pairs = [
    ("identical", build(7), build(7), True),
    ("one value differs", build(7), build(8), False),
    ("one node missing", build(7), TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5))), False),
    ("both empty", None, None, True),
    ("one empty", build(7), None, False),
    ("same values, other shape", TreeNode(1, TreeNode(2)), TreeNode(1, None, TreeNode(2)), False),
]
for label, p, q, expected in pairs:
    print(label, "| first levels:", levels(p), "| second levels:", levels(q), "| same:", expected)

Most rows announce themselves in the level lists. A differing value or a missing node shows up there directly. The last row is the exception, and it is the important one.

In the last row both level lists are [[1], [2]]. The lists match, and the trees still differ. The next section takes that row apart.

Intuition: matching level lists can hide a shape difference

A first idea compares summaries of the two trees. List each tree level by level, then compare the two lists. Equal lists feel like equal trees.

The summary throws away exactly the information this problem is about. A level list records which values sit at each depth. It does not record whether a lone child hangs on the left or on the right.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def levels_match(p, q):
    return levels(p) == levels(q)

a = TreeNode(1, TreeNode(2))
b = TreeNode(1, None, TreeNode(2))
print("levels of first:", levels(a))
print("levels of second:", levels(b))
print("level-list check says same:", levels_match(a, b))
print("correct answer: False, the 2 sits in a different slot")

The check says the trees match, and they do not. In the first tree the 2 is a left child. In the second it is a right child, and the left slot is empty.

The repair is to compare positions, not summaries. Walk both trees together, slot by slot. At each step, the two nodes in the same slot must both exist or both be missing, and their values must agree.

Brute force: collect every position, then compare

The straightforward method turns each tree into a list of entries. One entry holds a path and a value. The path is a string of L and R steps from the root, so it names the exact slot.

Two trees are the same exactly when their entry lists are equal. The method builds both lists in full before it compares anything, even when the roots already differ.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

entries_made = 0

def collect(node, path, out):
    global entries_made
    if node is None:
        return
    entries_made += 1
    out.append((path, node.value))
    collect(node.left, path + "L", out)
    collect(node.right, path + "R", out)

def brute_same(p, q):
    first = []
    second = []
    collect(p, "root", first)
    collect(q, "root", second)
    return first == second

a = TreeNode(1, TreeNode(2), TreeNode(3))
b = TreeNode(1, TreeNode(2), TreeNode(3))
c = TreeNode(1, None, TreeNode(2))
d = TreeNode(1, TreeNode(2))
print("identical pair:", brute_same(a, b))
print("entries for the right-leaning tree:")
entries = []
collect(c, "root", entries)
print(entries)
print("entries for the left-leaning tree:")
entries = []
collect(d, "root", entries)
print(entries)
print("shape pair same:", brute_same(c, d))

The paths expose what the level lists hid. One tree has its 2 at rootL and the other has it at rootR, so their entry lists differ. The answers are right on both pairs.

The cost is the full collection. Both trees are walked completely and stored, whatever the comparison would have found. A root mismatch on the first step still pays for the whole walk.

The optimal solution: walk both trees together

Recursion here means a function that compares one pair of nodes, then calls itself on the matching child pairs. The left child is compared with the left child, and the right with the right.

The key idea is one sentence. Two trees are the same exactly when their roots agree in value and both matching child pairs are the same, so the walk can stop and answer False at the first pair that disagrees.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def same(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.value != q.value:
        return False
    return same(p.left, q.left) and same(p.right, q.right)

def build(leaf_value):
    return TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(leaf_value)))

pairs = [
    ("identical", build(7), build(7)),
    ("one value differs", build(7), build(8)),
    ("one node missing", build(7), TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5)))),
    ("both empty", None, None),
    ("one empty", build(7), None),
    ("same values, other shape", TreeNode(1, TreeNode(2)), TreeNode(1, None, TreeNode(2))),
]
for label, p, q in pairs:
    print(label, "same:", same(p, q))

All six cases from the start of the article pass. The order of the checks inside the function matters. The two None checks come first, because asking a missing node for its value would fail.

The and between the two child calls is the early exit. When the left pair answers False, the right pair is never compared. Section 5 shows that saving happen.

Walkthrough: hunting the one differing leaf

Follow the pair where the last leaf differs, 7 in one tree and 8 in the other. Every pair before that leaf matches. The walk reaches the differing pair last, along the right edge of the tree.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def traced_same(p, q, path):
    if p is None and q is None:
        print("pair at", path, ": both empty, match")
        return True
    if p is None or q is None:
        print("pair at", path, ": one empty, mismatch")
        return False
    print("pair at", path, ":", p.value, "vs", q.value, "match" if p.value == q.value else "mismatch")
    if p.value != q.value:
        return False
    if not traced_same(p.left, q.left, path + " left"):
        return False
    return traced_same(p.right, q.right, path + " right")

def build(leaf_value):
    return TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(leaf_value)))

print("answer:", traced_same(build(7), build(8), "root"))

Read the order of the visits. The whole left subtree is settled before the right subtree begins. The pair at root right right is where the values 7 and 8 meet, and the walk answers False there without comparing anything after it.

In this pair there is nothing after it, because the differing node is a leaf and the last pair visited. Put the difference at the root instead, and the same walk ends after a single comparison, as section 6 counts.

Complexity

Time is O(n) in the worst case, where n is the smaller tree's node count. Identical trees force a full walk, and any mismatch can only shorten it.

Space is O(h), where h is the greater depth of the two trees. The call stack holds one frame per level on the current path, and no list of entries is built.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

compared = 0

def same(p, q):
    global compared
    compared += 1
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.value != q.value:
        return False
    return same(p.left, q.left) and same(p.right, q.right)

def balanced_of(values):
    if not values:
        return None
    mid = len(values) // 2
    return TreeNode(values[mid], balanced_of(values[:mid]), balanced_of(values[mid + 1:]))

for size in [3, 7, 15]:
    values = list(range(1, size + 1))
    compared = 0
    same(balanced_of(values), balanced_of(values))
    print("identical trees of", size, "nodes, pairs compared:", compared)
compared = 0
print("roots differ:", same(TreeNode(1, TreeNode(2)), TreeNode(9, TreeNode(2))), "pairs compared:", compared)

Identical trees cost one comparison per node, plus the comparisons of empty child pairs that close each branch. The root-mismatch case costs a single comparison in total. That gap is the early exit, measured.

Edge cases and pitfalls

Two empty trees are the same, and an empty tree never matches a filled one. Those two rules are the first two checks in the function, and they cover every missing-child comparison deeper in the walk.

Python's own equality is a trap here. Two separately built trees are different objects, so == between their roots answers False even when every value and slot matches. The structural walk is what answers True.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def same(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.value != q.value:
        return False
    return same(p.left, q.left) and same(p.right, q.right)

a = TreeNode(1, TreeNode(2), TreeNode(3))
b = TreeNode(1, TreeNode(2), TreeNode(3))
print("built separately, a == b:", a == b)
print("built separately, same(a, b):", same(a, b))
print("both empty:", same(None, None))
print("one empty:", same(a, None))
print("root value differs:", same(a, TreeNode(9, TreeNode(2), TreeNode(3))))
print("identical right chains:", same(TreeNode(1, None, TreeNode(2)), TreeNode(1, None, TreeNode(2))))
print("mirror chains:", same(TreeNode(1, TreeNode(2)), TreeNode(1, None, TreeNode(2))))

A second pitfall is comparing the wrong child pairs. Comparing the left child of one tree with the right child of the other tests mirror symmetry, not sameness. Two mirror-image trees would pass that check and fail this one, as the last line shows.

Order of the None checks is the third pitfall. Testing values before testing for None asks a missing node for its value. The run stops with an error instead of answering False.