# `Yog.Pathfinding.LCA`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/pathfinding/lca.ex#L1)

Lowest Common Ancestor (LCA) queries using binary lifting.

This module preprocesses a tree in O(V log V) time to answer LCA queries
and tree distance queries in O(log V) time per query.

## Algorithm

1. BFS from the root to compute depth and immediate parent for each node.
2. Build a binary lifting table where `up[k][v]` is the 2^k-th ancestor of v.
3. Answer LCA queries by lifting the deeper node up, then lifting both
   nodes together until their ancestors differ.

## Complexity

- **Preprocessing:** O(V log V)
- **LCA Query:** O(log V)
- **Distance Query:** O(log V)

## Example

    iex> tree = Yog.from_edges(:undirected, [{1, 2, 1}, {1, 3, 1}, {2, 4, 1}, {2, 5, 1}])
    iex> {:ok, state} = Yog.Pathfinding.LCA.lca_preprocess(tree, 1)
    iex> Yog.Pathfinding.LCA.lca(state, 4, 5)
    {:ok, 2}
    iex> Yog.Pathfinding.LCA.tree_distance(state, 4, 3)
    {:ok, 3}

## References

- https://cp-algorithms.com/graph/lca_binary_lifting.html

# `lca`

```elixir
@spec lca(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.node_id()} | {:error, :node_not_found}
```

Returns the lowest common ancestor of two nodes.

## Errors

  * `{:error, :node_not_found}` - One or both nodes are not in the tree

# `lca_preprocess`

```elixir
@spec lca_preprocess(Yog.Graph.t(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.LCA.State.t()} | {:error, :root_not_found | :not_a_tree}
```

Preprocesses the tree for LCA queries.

Returns `{:ok, state}` on success, or `{:error, reason}` if the graph
is not a valid tree connected at the given root.

## Errors

  * `{:error, :root_not_found}` - The root node does not exist in the graph
  * `{:error, :not_a_tree}` - The graph contains a cycle or is disconnected

# `tree_distance`

```elixir
@spec tree_distance(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, non_neg_integer()} | {:error, :node_not_found}
```

Calculates the tree distance (number of edges) between two nodes.

Computed as `depth[a] + depth[b] - 2 * depth[lca]`.

## Errors

  * `{:error, :node_not_found}` - One or both nodes are not in the tree

---

*Consult [api-reference.md](api-reference.md) for complete listing*