CPKit - Everything a Competitive Programmer Needs

Lowest Common Ancestor

AlgorithmsMedium

Query lowest common ancestors on trees using binary lifting tables.

Alt+Shift+L

Configuration Panel

Node U

Node V

Tree Layout Canvas

Double-click empty canvas to create root, select node to add child or delete.

Time Complexity

O(N log N) prep / O(log N) query

Auxiliary Space Complexity

O(N log N) parent tables

Conceptual Overview

Lowest Common Ancestor (LCA) of two nodes u and v in a tree is the deepest node that is an ancestor of both u and v.

Algorithm Mechanism

Binary lifting computes parents at heights $2^i$ using dynamic programming. To find LCA(u, v), first lift the deeper node to match depths, then elevate both nodes together until they share the same parent.

Source: CP-Algorithms reference guide