Skip to content
Tutorials Center
My learning

Topics

Lesson 105 of 225 ยท Trees

Tree Isomorphism and Tree Hashing

Decide whether two trees have the same shape: build canonical forms, assign subtree ids, handle unrooted trees with centers, and find duplicate subtrees.

Two trees are isomorphic if you can rename their nodes so that they become identical, in other words if they have the same shape. Think of two family trees drawn with different people's names: if the pattern of parents and children is the same, the trees are isomorphic. The question appears in compilers (are two expression trees structurally equal?), chemistry (do two molecules have the same skeleton?), file-system comparison and many contest problems.

Comparing every possible renaming is hopeless, so we use the standard trick: compute a canonical form for each tree, a description that is the same for every isomorphic tree and different for non-isomorphic ones. Then testing isomorphism is just comparing two values. This lesson builds canonical forms for rooted trees, turns them into small integer ids, extends the idea to unrooted trees, and uses it to find duplicate subtrees. You should know trees, tree traversals and hash tables.

Shape, not labels

In a rooted tree, the order of the children does not matter for shape. These two trees are isomorphic even though the children are listed in different orders:

flowchart TD
    subgraph T1["Tree 1"]
        a1["r"] --> b1["x"]
        a1 --> c1["y"]
        c1 --> d1["z"]
    end
    subgraph T2["Tree 2"]
        a2["r"] --> b2["p"]
        b2 --> c2["q"]
        a2 --> d2["s"]
    end

Both trees have a root with two children, one of which is a leaf and the other has one child.

The only data that matters is the multiset of child subtrees. If we can describe a subtree by something that depends only on the multiset of its children's descriptions, we have a canonical form.

The AHU idea: sorted parentheses

Aho, Hopcroft and Ullman gave a simple algorithm. Describe a leaf as (). Describe any other node as ( + the sorted descriptions of its children, joined together + ). Sorting removes the dependence on child order.

Example: a root with a leaf child and a child that has one leaf child becomes ((())()): the children are () and (()), which sort as (()) then () (the character ( is smaller than )), and are wrapped in parentheses.

Python Canonical strings for rooted trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The string is correct but can be long. For a tree with n nodes the strings have length 2n, and every level of the tree re-sorts and re-concatenates them, so a path-like tree takes O(n^2) time in the worst case. We can do better by never building the strings.

Replacing strings by ids

Give every distinct subtree shape a small integer id. A shape is determined by the sorted tuple of its children's ids, so keep a dictionary from such tuples to ids. Equal shapes automatically get the same id. This is the same idea as hash-consing and is exactly how you hash a tree without storing its text.

flowchart LR
    L["leaf: tuple () gets id 0"] --> P["parent: sorted tuple of child ids"]
    P --> D{"tuple in dictionary?"}
    D -- yes --> E["reuse its id"]
    D -- no --> F["assign the next free id"]

Each node gets the id of its shape: look up the sorted tuple of child ids.

Because the dictionary is shared between two trees, ids from different trees are comparable: equal ids mean equal shapes. The total work is O(n log n) for the sorts, plus the cost of hashing tuples whose total length is the sum of all degrees, which is n - 1.

Python Subtree ids with a shared dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Shape 0 is the leaf (empty tuple), shape 1 is a node with one leaf child, shape 2 is the shared root of tree1 and tree2, and shape 3 is the star. Comparing two integers replaces comparing whole trees.

Unrooted trees: use the center

Sometimes the root is not given: a tree is just a set of nodes and edges. An unrooted tree may be isomorphic to another one even if the two roots would be different nodes. The fix is to root the tree at a node that is determined by the shape itself, the center.

The center is found by repeatedly stripping off all current leaves. When one or two nodes remain, those are the centers. A tree has either one center or two adjacent centers. Then:

  • one center: root at it and take the canonical form;
  • two centers: compute the canonical form rooted at each and take the smaller one (compare the strings, or the id pair in sorted order).
flowchart LR
    A["Path with 5 nodes"] --> B["remove both ends:<br/>3 nodes left"]
    B --> C["remove both ends:<br/>1 node left"]
    C --> D["one center<br/>root here"]

Peeling leaves layer by layer ends at the center.

Python Isomorphism of unrooted trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop that strips leaves runs in O(n), and each canonical form costs O(n log n), so the whole test is O(n log n).

Finding duplicate subtrees

Subtree ids give an easy solution to a famous question: which subtrees appear more than once in a binary tree? Assign each subtree a shape id (for binary trees with left and right children in order, use the tuple (left_id, right_id) without sorting, because mirror images are different) and count how many times each id appears.

Python Count repeated subtrees in a binary tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here the leaf 4 repeats, and so does the subtree 2 -> 4. This is the same technique that compilers use for common subexpression elimination and that version-control systems use to deduplicate identical directories.

Pitfalls

  • Ordered vs unordered trees. Sort children only when child order does not matter. For binary trees or XML where order is meaningful, do not sort.
  • Do not hash by depth or size alone. Two different shapes can share both. Use full canonical forms or ids from a shared dictionary.
  • Randomized numeric hashes (a polynomial of child hashes) are shorter but can collide. If you use them, use a large modulus or two moduli and treat equality as probable; ids from a dictionary are exact.
  • Recursion depth. A path of 100,000 nodes breaks Python's default recursion limit. Convert to an iterative post-order traversal for large inputs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why are the children's descriptions sorted in the AHU canonical form?

    Isomorphic rooted trees may list their children in any order, so sorting gives all of them the same canonical description.
  2. 2. What does it mean when two nodes get the same shape id from a shared dictionary?

    The id is determined by the sorted tuple of child ids, so equal ids mean the same shape, recursively.
  3. 3. How many centers can a tree have?

    Peeling leaves layer by layer ends with one or two nodes. If two remain, they are connected by an edge.
  4. 4. When checking unrooted trees with two centers, what do we do?

    Using the minimum over both centers gives one value that does not depend on which center we start from.

Summary

  • Tree isomorphism asks whether two trees have the same shape; a canonical form turns it into an equality check.
  • For rooted trees, describe each node by the sorted descriptions of its children; replace strings by integer ids from a shared dictionary for speed.
  • For unrooted trees, root at the center (or take the minimum over two centers).
  • Subtree ids also find duplicate subtrees, which helps in compilers and storage systems. Keep child order when order matters.

Next: Heaps