Overview
Binary lifting stores the 2^k ancestor of each node, letting LCA queries raise nodes to equal depth and then jump upward together.
CoreSource checked
Binary Lifting LCA
Answers tree ancestor queries by precomputing powers-of-two jumps.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Tree Query Preprocessing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
ancestor tablepower-of-two jumpstree depthquery preprocessing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(n log n)
When to Use
- Use when analyzing graph structure needs ancestor table.
- Use when the input matches the assumptions behind tree Query Preprocessing.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Answers tree ancestor queries by precomputing powers-of-two jumps
- Uses ancestor table and power-of-two jumps to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Key Formulas (1)
Ancestor recurrence
up[v][j] = up[up[v][j − 1]][j − 1]
up[v][j] = up[up[v][j - 1]][j - 1]Builds each larger jump from two smaller jumps.
Pseudocode
- 1.Prepare the inputs and state needed for Binary Lifting LCA.
- 2.Apply the ancestor table step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Binary Lifting LCA input with a small representative case
- Output
- Visited nodes
- Explanation
- Binary Lifting LCA applies ancestor table to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the ancestor table step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Binary Lifting LCA look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Binary Lifting LCA.
graph-traversal-mechanismNotes
Binary Lifting LCA should be used with the assumptions and tradeoffs of tree Query Preprocessing in mind.
Sources (2)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Binary Lifting LCA's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Binary Lifting LCA's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withEuler Tour
Binary lifting and Euler tours are common alternative preprocessings for tree ancestor queries.
Related Algorithms
Tags
TreeLCADynamic ProgrammingBinary Lifting