Succinct data-structure for nearest colored node in a tree

Dekel Tsur

We give a succinct data-structure that stores a tree with colors on the nodes. Given a node x and a color alpha, the structure finds the nearest node to x with color alpha. This re…