Palindromic Tree (eertree) — Online Construction

Each appended character creates at most one new distinct palindrome. Watch the two roots, the suffix-link walk from last, and new palindrome nodes appear.

step 0

eertree (nodes, child edges & suffix links)

root (len -1, len 0) last (longest pal. suffix) new node suffix link

Nodes & current step

distinct palindromes = nodes − 2. Press Step to append the first character.
Two roots are created first: the imaginary root (len −1, parent of odd palindromes) and the empty root (len 0, parent of even palindromes). last starts at the empty root.
Self-contained visualization. The eertree stores every distinct palindromic substring as one node; each character adds at most one new node, so there are at most n+2 nodes. Solid grey arrows are child edges (U ⟶c⟶ cUc); dashed blue arrows are suffix links (to the longest proper palindromic suffix). See junior.md and professional.md for the proofs.