Balanced Parentheses and Succinct Tree Navigation

A tree with n nodes stored as records with child pointers costs Θ(n log n) bits at minimum, because each of the 2n or so pointers must be wide enough to name any node. A balanced-parentheses encoding stores the same tree in 2n + o(n) bits — two bits per node, plus a sublinear index — and answers parent, subtree-size, and depth queries in constant time, with child navigation needing one more index layer. The encoding is not a compression trick applied after the fact; it is a bijection between ordered trees and balanced strings, and the queries are arithmetic on the string.

The technique matters because it decouples the shape of a tree from the size of its nodes. A suffix tree over a text of n bytes has O(n) nodes and, in pointer form, occupies tens of bytes per node. In parentheses form the shape costs 2 bits per node and the satellite data — the edge labels, the leaf positions — lives in separate arrays indexed by node number. That separation is what makes multi-gigabyte text indexes possible at all.

The bijection

Walk the tree in depth-first order. On entering a node write (, on leaving write ). For a tree with n nodes the result is a string of 2n characters with n opens and n closes, balanced in the usual sense: every prefix has at least as many opens as closes, and the whole string has equal counts.

Every node corresponds to a matched pair, so nodes can be named by the position of their open parenthesis. Numbering nodes by preorder — the order in which their opens appear — turns the string position into the node number, but the two are not the same integer: the k-th node’s open sits at position select₁(k) among the opens, which in the combined string is a larger index. Implementations therefore store node payloads in a separate array indexed by preorder number, and recover the string position with a select when they need to navigate.

        A                string:  ( ( ) ( ( ) ( ) ) )
       / \               index:   0 1 2 3 4 5 6 7 8 9
      B   C
         / \             preorder:  A=0  B=1  C=2  D=3  E=4
        D   E            opens at:  0    1    3    4    6

Node A opens at 0 and closes at 9. Node C opens at 3 and closes at 8, so its subtree occupies positions 3 through 8 of the string. Node D opens at 4, closes at 5. The subtree of a node is a contiguous interval of the string, and that single fact is the source of most of the queries.

Subtree boundaries from matching parentheses

The close position of the node opening at i is the position of the parenthesis that matches it. Define excess(j) as the number of opens minus closes in [0, j), which at an open position is the depth of the node it opens. The matching close is the first position j > i whose character is a close and whose excess is excess(i) + 1; equivalently, it is j - 1 where j is the first position after i with excess(j) = excess(i). This is the classic “find the matching parenthesis” problem, and on a static string it is solved with a o(n) index.

One workable index stores, for each block of b parentheses, the minimum excess within the block and the excess at the block start. A search then skips blocks whose minimum exceeds the target, and scans within the one block that can contain the answer. With b = 256 and a second directory level over the block minima, the number of skipped entries stays bounded and the scan never leaves a single block.

A simpler alternative, sufficient for many queries, precomputes the match for every position at build time in 2n integers. That is 2n log n bits and defeats the purpose. The o(n) index is the point of the exercise.

Parent and child in constant time

Three derived operations cover most navigation, and each is a small combination of rank, select, and match.

Parent. The parent of the node with preorder number k is found by taking its open position i = select₁(k), then locating the last open before i whose excess is excess(i) - 1. Computing that directly needs a “find previous position with a given excess” operation, the backward analogue of the matching search, which uses the same block directory. The result is a string position, which converts back to a preorder number with one rank query.

Subtree size. If the node opens at i and its match is at j, the subtree contains (j - i + 1)/2 nodes. That is one subtraction, given the match. This is the query that makes the encoding attractive: in a pointer tree, subtree size is either stored per node (a field) or computed by a traversal.

The k-th child. Children of a node correspond to maximal runs of opens at excess excess(i)+1 inside the node’s interval. Finding the k-th requires skipping k-1 complete child subtrees, each of which is a match operation, so the cost is O(k) or O(log n) with an additional index over child counts. The O(1) child query needs a more elaborate structure than the basic encoding provides.

#include <stddef.h>
#include <stdint.h>

/* bp[] holds the 2n parentheses; i is the string position of an open.
   The parent is the last open before i at excess one less than i's. */
static size_t parent_of(const uint8_t *bp, size_t i) {
    int target = excess(bp, i) - 1;      /* excess at an open is its depth */
    for (size_t p = i; p-- > 0; ) {
        if (bp[p] == '(' && excess(bp, p) == target)
            return rank1(bp, p);         /* string position -> preorder number */
    }
    return (size_t)-1;                   /* i is the root: no position has excess -1 */
}

Depth is cheaper still: for the open at position i, depth = excess(i), because the excess at an open parenthesis counts exactly the ancestors whose parentheses have not yet been closed. That is one rank query, on the value at i, and no match lookup whatsoever.

The loop above is the naive version, O(n) worst case, and it is shown to make the invariant explicit. The production version replaces the scan with a block directory storing per-block minimum excess, which turns the backward search into a bounded number of block skips plus a scan of at most one block.

The extra index and what it costs

The encoding alone is 2 bits per node. Everything above needs rank/select on the excess sequence, and that is where the o(n) term comes from.

Two indexes are commonly layered on the string.

Rank/select on the parentheses themselves. rank₀(i) and rank₁(i) give the number of opens and closes before i; select of an open gives the position of the k-th node’s open. With n bits per character class and the standard two-level rank directory, this costs about 0.3 bits per stored bit, or 0.6 bits per node.

The excess directory. Block minima and block-start excess values, for the matching and parent searches. With 256-bit blocks and 32-bit values, that is 32/256 bits per position plus a top-level directory over the block values, roughly 0.25 bits per position, or 0.5 bits per node.

Total: about 2 bits per node for the string plus roughly 1.1 bits per node for the indexes. Compare a pointer representation at 64 bits per node for a single child pointer, or 128 bits for first-child and next-sibling, plus the node’s own payload. The saving is a factor of 40 or more in shape overhead, and the payload is unaffected because it lives in parallel arrays.

Where the queries get expensive

The O(1) claims are per query and assume the index is resident. Three costs are real.

Each query touches several arrays. A subtree-size query needs the string (2 bits per node), the match index, and the rank directory. At n = 10⁹ the string alone is 250 MB, so a query that walks the string at position i misses cache unless the access pattern is local. The smaller index arrays are the reason for the + o(n) term rather than the 2 bits per node; rounding each array up to a page boundary adds a further fixed waste, which is what dominates for trees of a few thousand nodes. This is why succinct trees are often used in a top-down traversal where the accessed positions are clustered, and why a random-access workload on a huge tree can be slower than a pointer tree despite doing less work.

Construction is not incremental. Building the string requires the tree in memory, and building the indexes requires a pass over the string. Both are O(n), but the constant is a full traversal plus several scans, and the intermediate representation (the tree) is exactly the pointer form the encoding was meant to avoid. The usual pattern is to build the tree, serialize, and free.

Updates are expensive. Inserting a leaf shifts every subsequent position in the string, which invalidates every index and every stored node number. The encoding is for static trees. Dynamic alternatives maintain a sequence of blocks with a two-level structure, which supports insertion in O(log n) and queries in O(log n) at a higher constant, and they are a different design rather than a patch on this one.

Variants that answer different questions

The plain balanced-parentheses encoding gives subtree size and parent. Other encodings trade the same 2 bits for different query sets, and the choice is driven by which queries dominate.

Depth-first unary degree sequence (DFUDS). Writes each node’s child count in unary — d opens followed by a close — which makes the k-th child a direct select and moves the cost to the parent query. Preferred when the workload descends rather than ascends.

Level-order unary degree sequence (LOUDS). Stores nodes in breadth-first order with unary degree codes, so the children of a node are contiguous and the parent of a node is found by a rank on the previous level. Its space is 2 bits per node and it suits breadth-first traversal.

Balanced parentheses with a leaf bitmap. For tries and suffix trees, most nodes are leaves, so storing a separate bitvector marking leaf opens lets the tree shape skip the leaves entirely. A suffix tree over a text of n characters has at most n leaves and n-1 internal nodes, and the internal shape costs 2 bits per internal node rather than per node.

The common thread is that all of these are rank/select structures over a bitvector, and all of them inherit the space and time characteristics of the underlying rank/select implementation described in Bitset Representation and Word-Level Rank and Select. A wavelet tree built over the node labels of such a tree — the technique in Wavelet Trees and Range Queries on Sequences — adds path queries that the shape alone cannot answer.

The accounting that justifies the complexity

A succinct tree is worth its index when the node payload is small relative to the shape overhead, or when the tree is an auxiliary structure that must be stored alongside data that is already large. A suffix tree over a genome, an XML document’s element hierarchy, a parse tree over a corpus: in each case the pointer representation’s shape cost is comparable to or larger than the data it indexes, and the 2-bits-per-node encoding changes what fits in memory.

It is not worth it when the tree is small enough that the index’s constant factors dominate, when the tree is mutable, or when the workload is a single full traversal. For a traversal, the pointer form’s locality is better and the encoding’s queries are never used. The structure earns its place in the narrow band where the tree is large, static, and queried by position rather than walked.