DSA Finding Duplicate Subtrees

The problem

A subtree is a node together with everything below it. A duplicate subtree is one shape with the same values appearing at two or more places in one tree.

The task lists each distinct duplicate once. A subtree appearing three times still appears once in the answer. Results print in sorted order, so the answer never depends on map order.

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

tree_a = TreeNode(1,
                  TreeNode(2, TreeNode(4)),
                  TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
tree_b = TreeNode(5,
                  TreeNode(3, TreeNode(1), TreeNode(4)),
                  TreeNode(8, TreeNode(6), TreeNode(9)))

print("Tree A duplicates expected:", sorted(['2[4[#,#],#]', '4[#,#]']))
print("Tree B duplicates expected:", [])

Tree A repeats a leaf and a small two-level subtree. Tree B repeats nothing. Both trees appear throughout the article.

Intuition: compare subtrees with each other

The first idea compares every pair of subtrees directly. Two subtrees match when their roots hold equal values and their children match in turn. The idea works, and its cost is the trap.

Each comparison can itself walk a whole subtree. A big tree holds many subtrees, and most pairs get compared and rejected the slow way. The same small subtree is re-examined inside every comparison that contains it.

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

steps = [0]
def same(a, b):
    steps[0] += 1
    if a is None or b is None:
        return a is None and b is None
    return a.value == b.value and same(a.left, b.left) and same(a.right, b.right)

x = TreeNode(2, TreeNode(4))
y = TreeNode(2, TreeNode(4))
z = TreeNode(2, None, TreeNode(4))
print("x matches y:", same(x, y), "node pairs visited:", steps[0])
steps[0] = 0
print("x matches z:", same(x, z), "node pairs visited:", steps[0])

Even a two-node comparison visits several node pairs. Shape matters as much as values. The subtree z holds the same values as x, in a different shape, and the comparison rightly rejects it.

Brute force: every pair of subtrees, compared

The brute force collects every subtree root in the tree. It then compares each pair of roots with the direct comparison. A matching pair marks a duplicate, recorded once and printed sorted at the end.

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

tree_a = TreeNode(1,
                  TreeNode(2, TreeNode(4)),
                  TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
tree_b = TreeNode(5,
                  TreeNode(3, TreeNode(1), TreeNode(4)),
                  TreeNode(8, TreeNode(6), TreeNode(9)))

steps = [0]
def same(a, b):
    steps[0] += 1
    if a is None or b is None:
        return a is None and b is None
    return a.value == b.value and same(a.left, b.left) and same(a.right, b.right)

def roots(node, out):
    if node is None:
        return
    roots(node.left, out)
    roots(node.right, out)
    out.append(node)

def name(node):
    if node is None:
        return "#"
    return str(node.value) + "[" + name(node.left) + "," + name(node.right) + "]"

for label, tree in [("Tree A", tree_a), ("Tree B", tree_b)]:
    rs = []
    roots(tree, rs)
    steps[0] = 0
    pairs = 0
    dup = set()
    for i in range(len(rs)):
        for j in range(i + 1, len(rs)):
            pairs += 1
            if same(rs[i], rs[j]):
                dup.add(name(rs[i]))
    print(label, "subtree roots:", len(rs), "pairs compared:", pairs,
          "node pairs visited:", steps[0])
    print(label, "duplicates:", sorted(dup))

The answers are right and the method is wasteful. Seven roots already mean 21 pair comparisons. Each comparison repeats walks that earlier comparisons finished. Naming a subtree once would end the repetition.

The optimal solution: name every subtree once

Serialising a subtree means writing it as one string that captures its root value and both child shapes. The marker # stands for an empty child, so two different shapes can never share a string.

A postorder walk builds each string from its two child strings, so every subtree is written exactly once. A frequency map counts the strings. A string reaching a count of two marks a duplicate, and later copies add nothing new.

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

tree_a = TreeNode(1,
                  TreeNode(2, TreeNode(4)),
                  TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
tree_b = TreeNode(5,
                  TreeNode(3, TreeNode(1), TreeNode(4)),
                  TreeNode(8, TreeNode(6), TreeNode(9)))

def serialise(node, counts, found):
    if node is None:
        return "#"
    left = serialise(node.left, counts, found)
    right = serialise(node.right, counts, found)
    text = str(node.value) + "[" + left + "," + right + "]"
    counts[text] = counts.get(text, 0) + 1
    if counts[text] == 2:
        found.append(text)
    return text

for label, tree in [("Tree A", tree_a), ("Tree B", tree_b)]:
    counts = {}
    found = []
    serialise(tree, counts, found)
    print(label, "distinct subtrees:", len(counts))
    print(label, "duplicate subtrees:", sorted(found))

Tree A reports the leaf and the two-level subtree, each once. Tree B reports an empty list. Sorting the found strings keeps the printed answer identical on every run.

Walkthrough: Tree A, subtree by subtree

Postorder visits the left subtree, then the right subtree, then the root. Each step finishes one string and updates its count. The walk below prints every step in finishing order.

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

tree_a = TreeNode(1,
                  TreeNode(2, TreeNode(4)),
                  TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
tree_b = TreeNode(5,
                  TreeNode(3, TreeNode(1), TreeNode(4)),
                  TreeNode(8, TreeNode(6), TreeNode(9)))

counts = {}
def walk(node):
    if node is None:
        return "#"
    left = walk(node.left)
    right = walk(node.right)
    text = str(node.value) + "[" + left + "," + right + "]"
    counts[text] = counts.get(text, 0) + 1
    print("finished", text, "- count now", counts[text])
    return text

walk(tree_a)
print("duplicates:", sorted(t for t, c in counts.items() if c >= 2))

The leaf string reaches a count of three by the end. It enters the answer when its count first reaches two. The root string appears once, so the whole tree is not its own duplicate.

Complexity

The serialisation visits each node once and builds one string per node, so it makes n string builds for n nodes. The strings themselves can total O(n^2) characters on a chain-shaped tree, and that total bounds the memory the map holds.

The brute force compares up to n squared pairs of subtrees. Each comparison can walk a whole subtree, so its cost grows far faster than one naming pass.

def build(depth):
    if depth == 0:
        return (4, None, None)
    sub = build(depth - 1)
    return (depth, sub, sub)

def size(t):
    if t is None:
        return 0
    return 1 + size(t[1]) + size(t[2])

for depth in [2, 3, 4]:
    t = build(depth)
    n = size(t)
    print("nodes", n, "- brute pairs up to:", n * (n - 1) // 2,
          " serialisation builds:", n)

The counts show the shape of the gap. Pair comparisons grow with the square of the node count. String builds grow with the node count itself. Bigger repeated trees widen the gap quickly.

Edge cases and pitfalls

Dropping the empty-child marker is the classic defect. Without it, a left-only child and a right-only child can produce the same string. Two different shapes then report as duplicates, and the answer lies.

Reporting a duplicate at every repeat is the second pitfall. A leaf appearing three times belongs in the answer once. The count reaching exactly two is the moment to record it.

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

tree_a = TreeNode(1,
                  TreeNode(2, TreeNode(4)),
                  TreeNode(3, TreeNode(2, TreeNode(4)), TreeNode(4)))
tree_b = TreeNode(5,
                  TreeNode(3, TreeNode(1), TreeNode(4)),
                  TreeNode(8, TreeNode(6), TreeNode(9)))

def serialise(node, counts, found):
    if node is None:
        return "#"
    left = serialise(node.left, counts, found)
    right = serialise(node.right, counts, found)
    text = str(node.value) + "[" + left + "," + right + "]"
    counts[text] = counts.get(text, 0) + 1
    if counts[text] == 2:
        found.append(text)
    return text

print("left shape string:", serialise(TreeNode(2, TreeNode(4)), {}, []))
print("right shape string:", serialise(TreeNode(2, None, TreeNode(4)), {}, []))
counts = {}
found = []
lone = TreeNode(1, TreeNode(2), TreeNode(3))
serialise(lone, counts, found)
print("no repeats, duplicates:", sorted(found))
print("empty tree string:", serialise(None, {}, []))

The left and right shapes print different strings, as they must. A tree with no repeats reports an empty list. The empty tree serialises to the bare marker and duplicates nothing.