LCA and binary lifting

The lowest common ancestor of vertices u and v is the deepest vertex that is an ancestor of both. Binary lifting is useful when the tree is static and many ancestor or path queries follow.

Recognition signals

• Many queries ask for an ancestor, LCA, or distance between two tree vertices.
• The root and edges do not change between queries.
• One O(V log V) preprocessing pass is affordable.

For only one LCA query, a parent walk or ordinary DFS may be simpler.

Preprocessed state

up[k][v] is the 2^k-th ancestor of v.

up[0][v] = parent[v]
up[k][v] = up[k - 1][ up[k - 1][v] ]  # two 2^(k-1) jumps

Also store depth[v]. Optionally store DFS entry and exit times when constant time ancestor checks are useful.

Query thinking flow

lca(u, v):
    if depth[u] < depth[v]: swap(u, v)

    lift u by the binary bits of depth[u] - depth[v]
    if u == v: return u                         # v was an ancestor

    for k from largest down to zero:
        if up[k][u] != up[k][v]:
            u = up[k][u]                       # stay below the LCA
            v = up[k][v]

    return parent[u]                            # first shared ancestor

Descending powers are essential: each accepted jump keeps the two vertices in different ancestor subtrees while moving them as high as safely possible.

flowchart LR
  accTitle: Lowest common ancestor query with binary lifting
  accDescr: First lift the deeper vertex to equal depth, return if the vertices meet, otherwise try jumps from largest to smallest while their ancestors differ, then return their shared parent.
  subgraph A1["1 · Align depth"]
    direction TB
    A["Query u and v"] --> B["Lift the deeper vertex<br/>by bits of the depth gap"]
    B --> C{"u equals v?"}
    C -->|"yes"| D["That vertex is the LCA"]
  end
  subgraph A2["2 · Stay below the LCA"]
    direction TB
    E["Scan powers<br/>largest to zero"] --> F{"Proposed ancestors differ?"}
    F -->|"yes"| G["Lift both vertices"]
    F -->|"no"| H["Reject that jump"]
    G --> I["Try next smaller power"]
    H --> I
  end
  C -->|"no"| E
  I --> J["Return parent of u<br/>first shared ancestor"]

The query has two phases with different goals: equalize depth, then maximize safe jumps that keep u and v in different subtrees.

Derived queries

• k-th ancestor: apply jumps for the set bits of k.
• Tree distance: depth[u] + depth[v] - 2 * depth[lca(u,v)].
• Number of edges or vertices on a path.
• Aggregate path queries when each jump table also stores a sum, minimum, maximum, or other associative value.

Complexity and traps

• Preprocessing: O(V log V).
• Each LCA or ancestor query: O(log V).
• Space: O(V log V).
• Define the root's parent consistently, often the root itself.
• Compute enough levels: ceil(log2(max(1, V))) + 1.
• Validate that the input is one tree, not a disconnected graph or cyclic graph.
• Recursive preprocessing can overflow on a chain.

Practice

• LeetCode: Lowest Common Ancestor of a Binary Tree

Tested template

PythonC++17C++11

class BinaryLiftingTree:
    """Answer lowest-common-ancestor queries on a fixed undirected tree."""

    def __init__(self, tree: Sequence[Sequence[int]], root: int = 0) -> None:
        _validate_vertex(root, len(tree), "root")
        _validate_unweighted_graph(tree)
        neighbor_sets = [set(neighbors) for neighbors in tree]
        if any(
            len(neighbors) != len(neighbor_sets[node])
            for node, neighbors in enumerate(tree)
        ):
            raise ValueError("input tree cannot contain parallel edges")
        if any(node in neighbors for node, neighbors in enumerate(neighbor_sets)):
            raise ValueError("input tree cannot contain self-loops")
        if sum(len(neighbors) for neighbors in tree) != 2 * (len(tree) - 1):
            raise ValueError("input must contain exactly n - 1 undirected edges")
        for node, neighbors in enumerate(neighbor_sets):
            if any(node not in neighbor_sets[neighbor] for neighbor in neighbors):
                raise ValueError("every tree edge must appear in both directions")
        self.depth = [0] * len(tree)
        parent = [-1] * len(tree)
        parent[root] = root
        stack = [root]
        while stack:
            node = stack.pop()
            for neighbor in tree[node]:
                if neighbor == parent[node]:
                    continue
                if parent[neighbor] != -1:
                    raise ValueError("input must be an undirected tree")
                parent[neighbor] = node
                self.depth[neighbor] = self.depth[node] + 1
                stack.append(neighbor)
        if any(ancestor == -1 for ancestor in parent):
            raise ValueError("input tree must be connected")

        levels = max(1, len(tree).bit_length())
        self.up = [parent]
        for _ in range(1, levels):
            previous = self.up[-1]
            # Doubling composes two jumps of length 2^(level - 1).
            self.up.append([previous[previous[node]] for node in range(len(tree))])

    def lca(self, left: int, right: int) -> int:
        _validate_vertex(left, len(self.depth), "left")
        _validate_vertex(right, len(self.depth), "right")
        if self.depth[left] < self.depth[right]:
            left, right = right, left

        difference = self.depth[left] - self.depth[right]
        for level in range(len(self.up)):
            if difference & (1 << level):
                left = self.up[level][left]
        if left == right:
            return left

        for level in range(len(self.up) - 1, -1, -1):
            if self.up[level][left] != self.up[level][right]:
                # Lift together while their 2^level ancestors still differ.
                left = self.up[level][left]
                right = self.up[level][right]
        return self.up[0][left]

class BinaryLiftingTree {
 public:
  explicit BinaryLiftingTree(const std::vector<std::vector<int>>& tree,
                             int root = 0)
      : depth_(tree.size(), 0) {
    validate_vertex(root, tree.size(), "root");
    for (const auto& neighbors : tree) {
      for (const int neighbor : neighbors) {
        validate_vertex(neighbor, tree.size(), "neighbor");
      }
    }
    std::vector<std::set<int>> neighbor_sets(tree.size());
    std::size_t directed_edge_count = 0;
    for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
      neighbor_sets[node].insert(tree[node].begin(), tree[node].end());
      if (neighbor_sets[node].size() != tree[node].size()) {
        throw std::invalid_argument("input tree cannot contain parallel edges");
      }
      if (neighbor_sets[node].count(node) != 0) {
        throw std::invalid_argument("input tree cannot contain self-loops");
      }
      directed_edge_count += tree[node].size();
    }
    if (directed_edge_count != 2 * (tree.size() - 1)) {
      throw std::invalid_argument(
          "input must contain exactly n - 1 undirected edges");
    }
    for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
      for (const int neighbor : neighbor_sets[node]) {
        if (neighbor_sets[neighbor].count(node) == 0) {
          throw std::invalid_argument(
              "every tree edge must appear in both directions");
        }
      }
    }
    std::vector<int> parent(tree.size(), -1);
    parent[root] = root;
    std::vector<int> stack(1, root);
    while (!stack.empty()) {
      const int node = stack.back();
      stack.pop_back();
      for (const int neighbor : tree[node]) {
        if (neighbor == parent[node]) {
          continue;
        }
        if (parent[neighbor] != -1) {
          throw std::invalid_argument("input must be an undirected tree");
        }
        parent[neighbor] = node;
        depth_[neighbor] = depth_[node] + 1;
        stack.push_back(neighbor);
      }
    }
    if (std::find(parent.begin(), parent.end(), -1) != parent.end()) {
      throw std::invalid_argument("input tree must be connected");
    }

    int levels = 1;
    while ((1LL << levels) <= static_cast<long long>(tree.size())) {
      ++levels;
    }
    up_.push_back(parent);
    for (int level = 1; level < levels; ++level) {
      up_.push_back(std::vector<int>(tree.size()));
      for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
        // Doubling composes two jumps of length 2^(level - 1).
        up_[level][node] = up_[level - 1][up_[level - 1][node]];
      }
    }
  }

  int lca(int left, int right) const {
    validate_vertex(left, depth_.size(), "left");
    validate_vertex(right, depth_.size(), "right");
    if (depth_[left] < depth_[right]) {
      std::swap(left, right);
    }
    int difference = depth_[left] - depth_[right];
    for (int level = 0; level < static_cast<int>(up_.size()); ++level) {
      if ((difference & (1 << level)) != 0) {
        left = up_[level][left];
      }
    }
    if (left == right) {
      return left;
    }
    for (int level = static_cast<int>(up_.size()) - 1; level >= 0; --level) {
      if (up_[level][left] != up_[level][right]) {
        // Lift together while their 2^level ancestors still differ.
        left = up_[level][left];
        right = up_[level][right];
      }
    }
    return up_[0][left];
  }

 private:
  std::vector<int> depth_;
  std::vector<std::vector<int>> up_;
};

class BinaryLiftingTree {
 public:
  explicit BinaryLiftingTree(const std::vector<std::vector<int>>& tree,
                             int root = 0)
      : depth_(tree.size(), 0) {
    validate_vertex(root, tree.size(), "root");
    for (const auto& neighbors : tree) {
      for (const int neighbor : neighbors) {
        validate_vertex(neighbor, tree.size(), "neighbor");
      }
    }
    std::vector<std::set<int>> neighbor_sets(tree.size());
    std::size_t directed_edge_count = 0;
    for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
      neighbor_sets[node].insert(tree[node].begin(), tree[node].end());
      if (neighbor_sets[node].size() != tree[node].size()) {
        throw std::invalid_argument("input tree cannot contain parallel edges");
      }
      if (neighbor_sets[node].count(node) != 0) {
        throw std::invalid_argument("input tree cannot contain self-loops");
      }
      directed_edge_count += tree[node].size();
    }
    if (directed_edge_count != 2 * (tree.size() - 1)) {
      throw std::invalid_argument(
          "input must contain exactly n - 1 undirected edges");
    }
    for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
      for (const int neighbor : neighbor_sets[node]) {
        if (neighbor_sets[neighbor].count(node) == 0) {
          throw std::invalid_argument(
              "every tree edge must appear in both directions");
        }
      }
    }
    std::vector<int> parent(tree.size(), -1);
    parent[root] = root;
    std::vector<int> stack(1, root);
    while (!stack.empty()) {
      const int node = stack.back();
      stack.pop_back();
      for (const int neighbor : tree[node]) {
        if (neighbor == parent[node]) {
          continue;
        }
        if (parent[neighbor] != -1) {
          throw std::invalid_argument("input must be an undirected tree");
        }
        parent[neighbor] = node;
        depth_[neighbor] = depth_[node] + 1;
        stack.push_back(neighbor);
      }
    }
    if (std::find(parent.begin(), parent.end(), -1) != parent.end()) {
      throw std::invalid_argument("input tree must be connected");
    }

    int levels = 1;
    while ((1LL << levels) <= static_cast<long long>(tree.size())) {
      ++levels;
    }
    up_.push_back(parent);
    for (int level = 1; level < levels; ++level) {
      up_.push_back(std::vector<int>(tree.size()));
      for (int node = 0; node < static_cast<int>(tree.size()); ++node) {
        // Doubling composes two jumps of length 2^(level - 1).
        up_[level][node] = up_[level - 1][up_[level - 1][node]];
      }
    }
  }

  int lca(int left, int right) const {
    validate_vertex(left, depth_.size(), "left");
    validate_vertex(right, depth_.size(), "right");
    if (depth_[left] < depth_[right]) {
      std::swap(left, right);
    }
    int difference = depth_[left] - depth_[right];
    for (int level = 0; level < static_cast<int>(up_.size()); ++level) {
      if ((difference & (1 << level)) != 0) {
        left = up_[level][left];
      }
    }
    if (left == right) {
      return left;
    }
    for (int level = static_cast<int>(up_.size()) - 1; level >= 0; --level) {
      if (up_[level][left] != up_[level][right]) {
        // Lift together while their 2^level ancestors still differ.
        left = up_[level][left];
        right = up_[level][right];
      }
    }
    return up_[0][left];
  }

 private:
  std::vector<int> depth_;
  std::vector<std::vector<int>> up_;
};

Construction validates a connected acyclic input and uses an explicit stack. Queries first align depth, then lift both vertices from the largest jump down.