Skip to content

Tree Isomorphism Ladder

This lane is for the first time a tree problem stops being about values on the tree and becomes purely about whether two trees have the same shape.

Who This Is For

Use this lane if:

  • Trees already feels comfortable
  • you can root a tree and think parent/child without trouble
  • child order is irrelevant and that is now the whole point

This lane is intentionally narrow:

  • one exact starter
  • one flagship rooted benchmark
  • one clear unrooted stretch by trying centers

Warm-Up

  • explain the difference between rooted and unrooted tree isomorphism
  • explain why child order must be forgotten
  • explain why sorted child signatures beat brute-force child permutation

Target skill:

  • recognize when a tree statement is about canonical structure, not path/query data

Core

  • rooted unordered trees
  • postorder canonical encoding
  • one shared interner across both trees
  • exact flagship rep: Tree Isomorphism I

Target skill:

  • trust the bottom-up canonical-type route and compare root types directly

Stretch

  • unrooted route -> try one or two centers first
  • compare rooted-first Tree Isomorphism I against the unrooted sibling Tree Isomorphism II
  • compare this lane against Virtual Tree when the problem is still structural but query-local

Target skill:

  • see unrooted tree isomorphism as one center-normalization step, not as a different family

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. reopen Trees just enough to stabilize rooted-tree language
  2. learn the rooted canonical route in Tree Isomorphism
  3. solve Tree Isomorphism I
  4. only then stretch to the unrooted center-rooting sibling

Exit Criteria

You are ready to move on when:

  • you stop thinking in terms of child permutations directly
  • you know rooted tree isomorphism is one bottom-up canonicalization problem
  • you know unrooted tree isomorphism means one or two center roots, not arbitrary rooting

External Practice