Palindromic Tree (Eertree)

Problem Overview

Attribute	Value
Difficulty	Hard
Category	String Algorithms / Data Structures
Key Technique	Suffix Links, Tree Construction
Invented By	Mikhail Rubinchik (2014)

Concept Explanation

The Palindromic Tree (also called Eertree) is a data structure that efficiently represents all distinct palindromic substrings of a string. Unlike tries or suffix trees, it has exactly two root nodes:

Odd Root (-1): Represents palindromes of odd length (conceptual length -1)
Even Root (0): Represents palindromes of even length (conceptual length 0)

Each node in the tree represents a unique palindromic substring, and edges are labeled with characters.

Learning Goals

After studying this topic, you will be able to:

Understand the two-root structure of palindromic trees
Build a palindromic tree in O(n) time
Count all distinct palindromic substrings efficiently
Find the longest palindromic substring
Use suffix links to navigate between palindromes

Intuition: How to Think About This Structure

Why Two Roots?

Key Insight: Palindromes can have odd or even length, requiring different “base cases.”

Odd-length palindromes like “aba” have a center character
Even-length palindromes like “abba” have no center character

The odd root (length -1) allows us to build single characters: adding ‘a’ to both sides of length -1 gives length 1 (“a”). The even root (length 0) allows us to build pairs: adding ‘a’ to both sides of length 0 gives length 2 (“aa”).

Core Components

Component	Purpose
Node	Represents a distinct palindrome
Edge (child)	Adding character c to both ends
Suffix Link	Points to longest proper palindromic suffix
Length	Length of palindrome this node represents

Suffix Link Intuition

The suffix link of a palindrome P points to the longest palindromic suffix of P (excluding P itself).

Example: "abaaba"
  Node for "abaaba" -> suffix link -> Node for "aba"
  Node for "aba"    -> suffix link -> Node for "a"
  Node for "a"      -> suffix link -> Odd root

Structure Definition

Node Structure

Node:
  - length: int          # Length of this palindrome
  - children: map[char -> node]  # Transitions by adding char to both ends
  - suffix_link: node    # Longest proper palindromic suffix
  - count: int           # (optional) Occurrences in string

Tree Properties

Property	Value
Max Nodes	n + 2 (at most n distinct palindromes + 2 roots)
Time Complexity	O(n) amortized for construction
Space Complexity	O(n * alphabet_size)

Dry Run: Building Tree for “abaaba”

Let’s trace the construction step by step.

Initial State

Nodes:
  Node 0 (Even Root): length=0, suffix_link -> Node 1
  Node 1 (Odd Root):  length=-1, suffix_link -> Node 1

Current suffix node: Node 1 (odd root)
String processed: ""

Step 1: Add ‘a’ (index 0)

Current: Node 1 (odd root, length=-1)
Check: Can we extend? Position 0 - (-1) - 1 = 0 >= 0? Yes
       s[0] == s[0]? 'a' == 'a'? Yes (trivially, single char)

Create Node 2: length = -1 + 2 = 1, represents "a"
Find suffix link: Follow from odd root -> odd root
                  Node 1 is odd root, suffix_link = Node 1
                  New palindrome suffix link -> Node 1

Tree state:
  Odd Root (1) --'a'--> Node 2 ("a")
  Node 2.suffix_link -> Node 1

Current suffix: Node 2

Step 2: Add ‘b’ (index 1)

Current: Node 2 ("a", length=1)
Check: Position 1 - 1 - 1 = -1 < 0? Yes, cannot extend
Follow suffix_link: Node 2 -> Node 1 (odd root)

Current: Node 1 (odd root, length=-1)
Check: Position 1 - (-1) - 1 = 1 >= 0? Yes
       s[1] == s[1]? 'b' == 'b'? Yes

Create Node 3: length = -1 + 2 = 1, represents "b"
Suffix link -> Node 1 (odd root)

Tree state:
  Odd Root (1) --'a'--> Node 2 ("a")
  Odd Root (1) --'b'--> Node 3 ("b")

Current suffix: Node 3

Step 3: Add ‘a’ (index 2)

Current: Node 3 ("b", length=1)
Check: Position 2 - 1 - 1 = 0 >= 0? Yes
       s[0] == s[2]? 'a' == 'a'? Yes!

Create Node 4: length = 1 + 2 = 3, represents "aba"
Find suffix link: Follow Node 3.suffix_link -> Node 1
                  From Node 1, can we extend with 'a'?
                  Node 1 already has child 'a' -> Node 2
                  Suffix link -> Node 2 ("a")

Tree state:
  Node 3 ("b") --'a'--> Node 4 ("aba")
  Node 4.suffix_link -> Node 2 ("a")

Current suffix: Node 4

Step 4: Add ‘a’ (index 3)

Current: Node 4 ("aba", length=3)
Check: Position 3 - 3 - 1 = -1 < 0? Yes, cannot extend
Follow suffix_link: Node 4 -> Node 2 ("a")

Current: Node 2 ("a", length=1)
Check: Position 3 - 1 - 1 = 1 >= 0? Yes
       s[1] == s[3]? 'b' != 'a'? No
Follow suffix_link: Node 2 -> Node 1 (odd root)

Current: Node 1 (odd root, length=-1)
Check: s[3] == s[3]? 'a' == 'a'? Yes
       Node 1 already has child 'a' -> Node 2

Current suffix: Node 2 (no new node created, "a" exists)

Step 5: Add ‘b’ (index 4)

Current: Node 2 ("a", length=1)
Check: Position 4 - 1 - 1 = 2 >= 0? Yes
       s[2] == s[4]? 'a' != 'b'? No
Follow suffix_link: Node 2 -> Node 1 (odd root)

Current: Node 1 (odd root)
Node 1 has child 'b' -> Node 3

Current suffix: Node 3 (no new node)

Step 6: Add ‘a’ (index 5)

Current: Node 3 ("b", length=1)
Check: Position 5 - 1 - 1 = 3 >= 0? Yes
       s[3] == s[5]? 'a' == 'a'? Yes!
       Node 3 already has child 'a' -> Node 4 ("aba")

But wait - we need to check for longer palindrome first!

From Node 4 ("aba"): Position 5 - 3 - 1 = 1 >= 0
       s[1] == s[5]? 'b' != 'a'? No

From Node 2 ("a"): Position 5 - 1 - 1 = 3 >= 0
       s[3] == s[5]? 'a' == 'a'? Yes!
       Check even: Can we create "aa"?

From Even Root (0): Position 5 - 0 - 1 = 4 >= 0
       s[4] == s[5]? 'b' != 'a'? No

Create Node 5: From Node 4, extend to get "abaaba" (length 6)
Wait - let me recalculate properly...

Actually from current suffix Node 3:
- Node 3 has child 'a' -> Node 4 ("aba")
- From Node 4: check s[5-3-1]=s[1]='b' vs s[5]='a' -> No match
- Follow Node 4.suffix_link -> Node 2
- From Node 2: check s[5-1-1]=s[3]='a' vs s[5]='a' -> Match!
- Node 2 has child 'a'? No -> Create Node 5 ("aa", length 2)

Create Node 5: length=2, represents "aa"
Suffix link for "aa" -> Node 2 ("a")

Continue checking for longer:
From Node 5 ("aa"): check s[5-2-1]=s[2]='a' vs s[5]='a' -> Match!
Check if Node 5 has child 'a'? No -> Create Node 6

Create Node 6: length=4, represents "aaa"...

Wait, that's wrong. Let me redo this more carefully.

Corrected Step 6: Add ‘a’ (index 5)

String so far: "abaab" + "a" = "abaaba"
Current suffix: Node 3 ("b")

Find longest palindrome ending at position 5:
1. Start from last suffix node: Node 3 ("b", length=1)
2. Check if we can extend: s[5-1-1]=s[3]='a', s[5]='a' -> Match!
3. Does Node 3 have edge 'a'? Yes -> Node 4 ("aba")
4. From Node 4 (length=3): s[5-3-1]=s[1]='b', s[5]='a' -> No match
5. Follow suffix link: Node 4 -> Node 2 ("a", length=1)
6. From Node 2: s[5-1-1]=s[3]='a', s[5]='a' -> Match!
7. Does Node 2 have edge 'a'? No

Create Node 5: length = 1 + 2 = 3... wait that creates "aaa"

Let me reconsider. Node 2 is "a". Adding 'a' to both sides of "a"
gives "aaa" which doesn't match our string.

Going to Even Root (length=0):
From Even Root: s[5-0-1]=s[4]='b', s[5]='a' -> No match

Back to Odd Root (length=-1):
From Odd Root: always matches (single char)
Create child 'a' if not exists -> Node 2 exists

So current suffix = Node 2, and we found "abaaba"!

Actually for "abaaba", the longest palindrome ending at index 5 IS "abaaba".
Let me trace finding it:

From Node 3 -> extend with 'a' -> Node 4 ("aba")
From Node 4 -> can we extend with 'a'?
  s[5-3-1]=s[1]='b' vs s[5]='a' -> No

Hmm, but "abaaba" IS a palindrome. The issue is we haven't created it yet.

Actually starting fresh from Node 4's suffix link:
Node 4.suffix_link = Node 2 ("a")
From Node 2: s[3]='a' == s[5]='a' -> can extend!
Node 2 has no child 'a' yet for even extension...

Create Node 5: from EVEN ROOT with 'a'
  Check: s[4]='b' != s[5]='a' -> cannot create "aa"

So we go back and the longest new palindrome ending at 5 is just "a" (reusing Node 2).

Then we must build "abaaba" differently. From Node 4 ("aba"):
We need to find if "abaaba" can be formed.
From Even Root: s[4]='b' != s[5]='a', cannot extend
From Node 4's parent edge...

The key is: From Node 4 ("aba"), s[1] != s[5], so we cannot extend.
Current suffix becomes Node 2 after following links.

Final Tree Structure for “abaaba”

          Odd Root (-1)
          /         \
       'a'           'b'
        |             |
    Node 2 "a"    Node 3 "b"
        |             |
       'a'           'a'
        |             |
   Node 5 "aa"   Node 4 "aba"
                      |
                     'a'
                      |
                Node 6 "abaaba"

Distinct palindromes: "a", "b", "aa", "aba", "abaaba"
Total: 5 distinct palindromic substrings

Common Mistakes

Mistake 1: Incorrect Suffix Link Updates

# WRONG: Not following suffix links properly
def get_suffix_link(node, pos, s):
  return node.suffix_link  # Too simple!

# CORRECT: Must verify the palindrome condition
def get_suffix_link(node, pos, s):
  cur = node.suffix_link
  while pos - cur.length - 1 < 0 or s[pos - cur.length - 1] != s[pos]:
    cur = cur.suffix_link
  return cur

Problem: Suffix links must point to valid palindromic suffixes. Fix: Always verify boundary and character match conditions.

Mistake 2: Boundary Check Errors

# WRONG: Missing boundary check
if s[pos - cur.length - 1] == s[pos]:  # May access negative index!

# CORRECT: Check boundary first
if pos - cur.length - 1 >= 0 and s[pos - cur.length - 1] == s[pos]:

Mistake 3: Forgetting Even Root’s Suffix Link

# WRONG: Even root suffix link to itself
even_root.suffix_link = even_root

# CORRECT: Even root points to odd root
even_root.suffix_link = odd_root  # Allows falling back to single chars

Edge Cases

Case	Input	Behavior	Notes
Empty string	””	Only roots exist	0 palindromes
Single char	“a”	1 palindrome	Just “a”
All same chars	“aaaa”	n palindromes	“a”, “aa”, “aaa”, “aaaa”
No repeats	“abcd”	n palindromes	Only single characters
All pairs	“aabb”	4 palindromes	“a”, “b”, “aa”, “bb”

When to Use Palindromic Tree

Use This Approach When:

Counting distinct palindromic substrings
Finding all palindromes in O(n) time
Need occurrence count of each palindrome
Building incrementally (online algorithm)

Don’t Use When:

Only need longest palindrome (Manacher’s is simpler)
Memory is extremely constrained
String is very short (brute force is fine)

Comparison with Alternatives

Algorithm	Time	Space	Use Case
Palindromic Tree	O(n)	O(n)	All distinct palindromes
Manacher’s	O(n)	O(n)	Longest palindrome only
Brute Force	O(n^3)	O(1)	Very short strings
Hashing	O(n^2)	O(n)	Counting with collision risk

Solutions

Python Implementation

class PalindromicTree:
  def __init__(self):
    self.nodes = []
    # Node 0: even root (length 0)
    # Node 1: odd root (length -1)
    self.nodes.append({'len': 0, 'suffix': 1, 'children': {}})
    self.nodes.append({'len': -1, 'suffix': 1, 'children': {}})
    self.last = 1  # Start from odd root
    self.s = ""

  def _get_link(self, v, pos):
    """Find node where we can extend with s[pos]."""
    while True:
      cur_len = self.nodes[v]['len']
      if pos - cur_len - 1 >= 0 and self.s[pos - cur_len - 1] == self.s[pos]:
        return v
      v = self.nodes[v]['suffix']

  def add(self, c):
    """Add character c to the tree. Returns True if new palindrome created."""
    pos = len(self.s)
    self.s += c

    # Find longest palindrome that can be extended
    cur = self._get_link(self.last, pos)

    if c in self.nodes[cur]['children']:
      self.last = self.nodes[cur]['children'][c]
      return False  # Palindrome already exists

    # Create new node
    new_node = len(self.nodes)
    new_len = self.nodes[cur]['len'] + 2
    self.nodes.append({
      'len': new_len,
      'suffix': 1,  # Will update below
      'children': {}
    })
    self.nodes[cur]['children'][c] = new_node

    # Find suffix link for new node
    if new_len == 1:
      self.nodes[new_node]['suffix'] = 0  # Single char -> even root
    else:
      suffix_parent = self._get_link(self.nodes[cur]['suffix'], pos)
      self.nodes[new_node]['suffix'] = self.nodes[suffix_parent]['children'][c]

    self.last = new_node
    return True  # New palindrome created

  def count_distinct(self):
    """Return count of distinct palindromic substrings."""
    return len(self.nodes) - 2  # Exclude two roots

  def build(self, s):
    """Build tree for entire string."""
    for c in s:
      self.add(c)
    return self.count_distinct()


# Example usage
def count_palindromic_substrings(s):
  """Count distinct palindromic substrings in s."""
  tree = PalindromicTree()
  return tree.build(s)


def get_longest_palindrome(s):
  """Find the longest palindromic substring."""
  tree = PalindromicTree()
  tree.build(s)

  max_len = 0
  max_node = -1
  for i in range(2, len(tree.nodes)):
    if tree.nodes[i]['len'] > max_len:
      max_len = tree.nodes[i]['len']
      max_node = i

  # Reconstruct palindrome (simplified - returns length)
  return max_len


# Test
if __name__ == "__main__":
  s = "abaaba"
  print(f"Distinct palindromes in '{s}': {count_palindromic_substrings(s)}")
  print(f"Longest palindrome length: {get_longest_palindrome(s)}")

Applications

1. Count Distinct Palindromic Substrings

The number of nodes (excluding roots) equals distinct palindromes.

def count_distinct(s):
  tree = PalindromicTree()
  tree.build(s)
  return tree.count_distinct()  # nodes - 2

2. Longest Palindromic Substring

Track maximum length node during construction.

def longest_palindrome(s):
  tree = PalindromicTree()
  tree.build(s)
  return max(node['len'] for node in tree.nodes[2:])

3. Count Total Palindrome Occurrences

Use suffix links to propagate counts.

def count_occurrences(s):
  tree = PalindromicTree()
  tree.build(s)
  # Each node is visited once per occurrence
  # Propagate via suffix links in reverse order

Problem	Connection
Longest Palindrome	Find longest palindromic substring
Required Substring	String pattern matching

Key Takeaways

Two Roots: Odd root (length -1) and even root (length 0) handle different palindrome parities
Linear Time: O(n) construction despite complex structure
Suffix Links: Enable efficient navigation to longest palindromic suffix
Node Count: At most n distinct palindromic substrings in any string of length n

Practice Checklist

Implement palindromic tree from scratch
Trace construction on paper for a small string
Solve “count distinct palindromes” problem
Compare with Manacher’s algorithm for longest palindrome
Understand suffix link computation