December 20, 2025 | 4 Minute Read

Eertree (or palindrome tree) is a data structure used for searching palindromes in a string. It was invented in 2015 by Mikhail Rubinchik and Arseny M. Shur. The name itself is a palindrome, derived from the word “tree”. The paper is pretty straightforward as far as papers go, but it can be a bit confusing at first.

It’s easier to understand when you see how it’s built step by step. You can use the textbox below to type a string and see how it would be represented in an eertree. You can also read through the description first and come back to try it out afterwards.

How it works

Before we dive into implementation details, let’s take a moment to classify palindromes into three types:

Single characters, pretty straightforward. 1.

A pair of the same character (eg: aa). All even-length palindromes have one in the middle. 1.

A pair of the same character “surrounding” another palindrome (type 1, 2 or 3).

As you can see, you can make a longer palindrome simply by adding the same character to both ends.

... a b c d c d a ...

Each node in an eertree (apart from the special nodes) represents a palindrome. Since we know that every single character is a palindrome by itself, these nodes become the building blocks for larger palindromes.

A character edge, represented in black and pointing downwards, means the character surrounds the source palindrome. If the source palindrome has length n, the target palindrome will have length n + 2. Here’s how it would look for the word “kayak”.

We show the palindrome strings inside the nodes to make things easier to understand, but this isn’t required in an actual implementation. Usually, you’d just keep track of the length of each palindrome.

Suffix edges, represented in blue and pointing upwards, connect a palindrome to the longest palindrome suffix it has. For example “eve” has a suffix edge to “e”, and “eveve” connects to “eve”. Each node has exactly one suffix edge. On the other hand, it can have zero or many character edges.

Special nodes

Character edges help us represent type 3 palindromes, but we need special nodes for type 1 and type 2 palindromes. An eertree has two special nodes for this purpose.

The imaginary root (or odd root) is a node with length -1. It has character edges to palindromes with a single character. The rule mentioned above still holds as the -1+2 would give us length of 1 for the target palindrome. Of course, a palindrome of length −1 can’t actually exist, which is why this node is called the imaginary root. Its suffix edge points to itself.

The empty root (or even root) is a node with length 0. It can only have character edges to palindromes of length 2. Its suffix edge points to the imaginary root.

Constructing an eertree

We build an eertree by adding characters from the string one by one. When we see a character for the first time, it gets added as a palindrome of length 1. We also keep track of the longest palindromic suffix of the string processed so far (shown in red, and referred to as the max suffix).

When adding a new character, we check whether the character immediately before the current max suffix matches the character we’re adding. If it does, we’ve successfully extended the palindrome. We then create a new node with length increased by 2 and add a character edge from the max suffix.

If it doesn’t match, we follow the suffix edge of the max suffix (which leads to a shorter palindrome) and repeat the same check. Eventually, we either find a match or end up at the imaginary root.

You can modify the example below to get a better feel for how this works.

There is a JavaScript implementation referenced on this page. You can find examples in many other languages on Rosetta Code. You can also write your own version depending on the problem you want to solve. For example, if you’re looking for the longest palindrome in a string, you can just return the just discovered (if there was one) palindrome’s length from add function. For other problems, you may need to implement a tree traversal.