Can a rooted tree answer arbitrary lowest-common-ancestor queries in constant time after only linear preprocessing? Yes. Schieber–Vishkin gives a classic solution: encode the tree into carefully chosen path labels and bitsets so that the query becomes a small number of machine-word operations and table lookups.
This Learning Hall article builds from the ordinary LCA problem through preorder structure, inlabel paths, ascendant masks and path heads, then connects the method to online-query workloads, bit-level engineering and the practical choice between Schieber–Vishkin, binary lifting, Euler-tour RMQ and Tarjan’s offline LCA.
Quick Read
- The lowest common ancestor LCA(u,v) is the deepest vertex that is an ancestor of both u and v.
- Schieber–Vishkin preprocesses a rooted tree in O(n) time and space and answers each online LCA query in O(1).
- Its central structure is an inlabel value that decomposes the tree into vertical paths.
- Nodes on the same vertical path share the same inlabel.
- The least significant set bit of an inlabel identifies the path’s level in an implicit perfect-binary-tree structure.
- An ascendant bitset records which inlabel-path levels occur on the route from a node to the root.
- A head table maps an inlabel to the highest node on that vertical path.
- Bit operations determine the target path containing the LCA; head lookups then move u and v to their entry points on that path.
- The algorithm is theoretically elegant but implementation-heavy; binary lifting is often simpler unless query volume or strict O(1) latency justifies the complexity.
1. Beginner Level: What Is LCA?
In a rooted tree, every node has a unique path to the root. For two nodes u and v, their lowest common ancestor is where those two root paths first merge when moving upward.
A
/ \
B C
/ \ \
D E F
LCA(D,E) = B
LCA(D,F) = A
LCA(C,F) = C
LCA appears in tree distances, ancestry queries, suffix-tree algorithms, network hierarchies, compiler analyses and many reductions from range-minimum queries.
2. Why Not Just Walk Upward?
The simplest method raises the deeper node until depths match, then moves both parents upward until they meet. Its worst-case query time is O(height), which becomes O(n) on a chain.
Binary lifting improves this to O(log n) queries after O(n log n) preprocessing. Euler-tour plus RMQ can achieve O(1) queries with suitable RMQ machinery. Schieber–Vishkin takes a different route: encode ancestry into word-sized bit patterns so the LCA path can be located directly.
For a contrasting offline method, see Tarjan’s Offline LCA Algorithm. Schieber–Vishkin owns the online constant-time-query job.
3. Preorder Gives Every Subtree an Interval
Run a DFS preorder. Every vertex receives an integer when first visited. A rooted subtree then occupies a contiguous interval of preorder numbers. This interval property lets the preprocessing choose a specially structured label from inside each subtree.
The original Schieber–Vishkin construction can be described through preorder and subtree size. Modern tutorials often present an equivalent leaf-number or DFS-order view. In both cases, bit structure in the chosen labels is what creates the vertical-path decomposition.
4. The inlabel Idea
Each node receives an inlabel. Intuitively, among the labels represented in its subtree, choose one whose binary form has the most significant useful trailing-power-of-two structure. A convenient implementation property is that the least significant set bit:
lsb(x) = x & -x
acts as a level marker. Ancestors can inherit an inlabel from a child when that child’s label has a larger least-significant-set-bit value.
5. inlabels Decompose the Tree Into Vertical Paths
The most useful mental model is simple:
- Nodes with the same inlabel lie on one vertical ancestor–descendant path.
- Moving from one such path to its parent path strictly increases the relevant lsb level.
- Therefore a root path crosses only O(log n) distinct inlabel paths even though the tree itself may be deep.
This resembles heavy-path decomposition in spirit, but the path selection is encoded specifically so that later bit tricks can identify the LCA path in constant time.
6. Build the head Table
For every inlabel value, store the highest node carrying that inlabel. Call it:
head[inlabel] = topmost node on that vertical path
If a query discovers that u must jump from its current inlabel path to some ancestor path, the head table identifies the entry boundary immediately. One parent step from an appropriate path head places us at the correct transition point.
7. The ascendant Bitset
For each node v, ascendant[v] is a machine-word bitset. A bit is set when the root-to-v route passes through an inlabel path whose lsb corresponds to that bit position.
ascendant[root] = path_bit(inlabel[root])
ascendant[v] = ascendant[parent[v]] | path_bit(inlabel[v])
Because path levels increase as we move toward the root, these bits form a compact summary of all vertical paths above v. Instead of storing O(log n) explicit path ancestors per vertex, one word can represent the set when n fits the machine-word model assumed by the algorithm.
8. What a Query Must Discover
For LCA(u,v), first determine the inlabel path that contains the true LCA. The inlabels of u and v can be viewed as nodes inside an implicit perfect binary tree determined by their bit patterns. Their most significant differing bit indicates where those virtual paths diverge.
But the true tree LCA may lie on an ancestor inlabel path above that first virtual meeting point. Intersecting:
ascendant[u] & ascendant[v]
reveals the path levels shared by both root routes. Masking away levels below the virtual divergence lets us select the lowest shared vertical path that can contain the actual LCA.
9. Bit Operations Replace a Search Loop
A modern implementation uses operations such as XOR, AND, least-significant-set-bit extraction and most-significant-set-bit/bit-floor extraction. Conceptually:
1. compare inlabel[u] and inlabel[v]
2. find their relevant divergence bit
3. intersect ascendant[u] and ascendant[v]
4. mask out vertical paths that are too low
5. isolate the target shared path bit
No loop proportional to tree depth or log n is needed during the query. This is where the O(1) online bound comes from.
10. Move u and v Onto the Target Path
If u already lies on the target inlabel path, keep u. Otherwise identify the highest lower path on u’s route that sits just below the target path, look up its head, and move to the parent of that head. Do the analogous operation for v.
After those constant-time jumps, both candidate vertices lie on the target path. The shallower one is the LCA.
11. Safe Query Skeleton
SCHIEBER_VISHKIN_LCA(u, v):
target_level = FIND_SHARED_INLABEL_LEVEL(
inlabel[u], inlabel[v],
ascendant[u], ascendant[v])
u2 = ENTRY_ON_TARGET_PATH(u, target_level,
inlabel, ascendant, head, parent)
v2 = ENTRY_ON_TARGET_PATH(v, target_level,
inlabel, ascendant, head, parent)
return shallower(u2, v2)
This skeleton is intentionally explicit about the two nontrivial bit-level helpers. Their exact formulas should be copied from a verified derivation or thoroughly tested reference implementation rather than reconstructed casually from memory.
12. Complexity
- Preorder, subtree information and inlabel construction: O(n).
- Ascendant and head construction: O(n).
- Memory: O(n).
- Each query: O(1) word operations and table accesses in the RAM model.
The original Schieber–Vishkin paper also emphasises parallelisation: linear sequential preprocessing can be transformed into logarithmic-time parallel preprocessing with an optimal processor count in the EREW PRAM model.
13. Schieber–Vishkin vs Binary Lifting
- Binary lifting: O(n log n) memory/preprocessing, O(log n) query, very easy to implement and audit.
- Schieber–Vishkin: O(n) preprocessing and memory, O(1) query, substantially more bit-level complexity.
If queries are not dominant, binary lifting may win in real engineering simply through clarity and smaller constants in surrounding code. If millions of LCA queries sit on a hot path, constant-time query machinery becomes more compelling.
14. Schieber–Vishkin vs Euler Tour + RMQ
Euler-tour LCA reduces each query to a range-minimum query over depths. With an O(1)-query static RMQ structure, it also reaches O(1) LCA queries. The difference is conceptual: Euler-tour methods transform LCA into another problem, while Schieber–Vishkin attacks ancestry directly with path labels and bit operations.
Our Cartesian Trees and Static RMQ article covers that neighbouring route. Keeping the two approaches separate avoids collision while making the trade-off visible.
15. Failure Modes
- Mixing different published inlabel conventions. Several equivalent expositions exist; formulas must match the preprocessing convention.
- Off-by-one preorder numbering. Bit identities change if a formula assumes 1-based labels but code uses 0-based labels.
- Undefined bit scans on zero. Guard equal-label and equal-node cases before calling count-leading-zero or bit-floor primitives.
- Signed-shift mistakes. Use unsigned integer types for masks and bit extraction.
- Word-size overflow. Confirm that n and all path masks fit the chosen word model.
- Incorrect head semantics. head must refer to the topmost node of an inlabel path under the same decomposition.
- Testing only balanced trees. Chains, stars and irregular trees expose path-boundary errors.
16. Professional Testing Strategy
- Compare every pair of vertices against a naive parent-walk oracle for small random trees.
- Test a chain, star, perfect binary tree and broom-shaped tree.
- Test u=v, root queries, parent–child pairs and siblings.
- Inspect nodes where inlabel changes between parent and child.
- Assert that nodes with equal inlabel form one ancestor–descendant path.
- Assert ascendant[v] contains every path bit encountered on the root-to-v route.
- Differential-test against binary lifting on millions of generated queries.
17. How to Learn It Efficiently
Do not begin with the final bit formula. First colour a tree by inlabel so each vertical path is visually obvious. Next compute only the least-significant-set-bit level for each path. Then build ascendant masks by hand on a ten-node example. Only after the learner can explain what each bit means should the constant-time query formula be introduced.
This is an ideal worked-example problem: fully annotate one query, fade the path labels on the next, then require the learner to reconstruct the mask. Programming-education reviews find code tracing, subgoal-labelled examples and incomplete examples useful scaffolds before independent code generation.
18. Practice Problems
- Number a small rooted tree in preorder and verify each subtree forms an interval.
- Compute inlabels and draw the induced vertical paths.
- Build ascendant masks and explain every set bit.
- Identify the target inlabel path for five LCA queries without returning the final node.
- Implement binary lifting first and use it as an oracle for Schieber–Vishkin.
- Benchmark one million LCA queries under both methods.
- Port the implementation from 64-bit to 32-bit words and document the maximum supported n.
19. Sources and Further Reading
- Baruch Schieber and Uzi Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization, SIAM Journal on Computing, 1988.
- Modern Schieber–Vishkin LCA tutorial with inlabel and ascendant derivation.
- Muldner, Jennings and Chiarelli, A Review of Worked Examples in Programming Activities, ACM TOCE, 2023.
- Using Adaptive Parsons Problems to Scaffold Write-Code Problems, ICER 2022.
Final idea: Schieber–Vishkin turns ancestry into representation. Instead of repeatedly climbing a tree, it gives each node a compact description of the vertical paths above it. The query then asks a bit-level question—which path do these two histories share lowest?—and uses one or two table jumps to recover the actual vertex.
