Lowest common ancestor in a BST

Why this matters

Many programs need the nearest shared parent of two items. A file system has folders inside folders. Two files may both sit under the folder projects, and the useful answer is the deepest folder that contains both. A company chart has managers over teams. The nearest manager who is above two employees is the first person who can settle a question about both.

In a tree, this shared parent is called the lowest common ancestor, or LCA. The word "ancestor" needs a plain definition first. The ancestors of a node are the nodes on the path from that node up to the root. In this lesson, a node also counts as its own ancestor. So the LCA of 4 and 4 is 4.

A general binary tree has no order, so finding the LCA there means searching both sides. A binary search tree, or BST, has order, and that order tells you which side to search. This lesson shows how to use the order to find the LCA with one walk from the root. The BST rule and the insert code come from the earlier lesson on BST property, insert and search. The code below repeats insert so each sample compiles on its own.

The tree and the answers

All examples use the nine-node tree below. The root holds 8.

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

Some LCA answers from this tree are these.

• The LCA of 4 and 7 is 6. Both 4 and 7 are below 6, and no node below 6 is above both of them.
• The LCA of 3 and 6 is 3. Node 3 is an ancestor of 6, so 3 is the answer.
• The LCA of 1 and 13 is 8. The value 1 is in the left subtree of 8 and the value 13 is in the right subtree, so only 8 is above both.
• The LCA of 4 and 4 is 4.

Keep the first answer in mind. Walking down the tree from the root, the first node that sits between 4 and 7 is 6. That is the key idea of this lesson.

The slow way: search both sides

A general binary tree, with no ordering, can find the LCA by searching. The rule is simple. Ask each child whether it contains p or q. If the left subtree has one of them and the right subtree has the other, the current node is the LCA. If one side returns a node, pass that node up.

Here is the code. It counts each node it enters, so you can compare the work.

#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
std::unique_ptr<Node> insert(std::unique_ptr<Node> root, int value) {
    if (!root) return std::make_unique<Node>(value);
    if (value < root->value) root->left = insert(std::move(root->left), value);
    else if (value > root->value) root->right = insert(std::move(root->right), value);
    return root;
}
 
const Node* generic_lca(const Node* node, int p, int q, int& visited) {
    if (node == nullptr) return nullptr;
    ++visited;
    if (node->value == p || node->value == q) return node;
    const Node* left = generic_lca(node->left.get(), p, q, visited);
    const Node* right = generic_lca(node->right.get(), p, q, visited);
    if (left != nullptr && right != nullptr) return node;
    return left != nullptr ? left : right;
}

The function returns the node it found, or nullptr when neither p nor q is at or below it. A nullptr is C++'s empty pointer. When both sides return a node, the current node is the split point. When only one side returns a node, that node is passed up.

The function has to search both children. It cannot know in advance which child holds p or q, because the tree has no order. So it visits most of the tree.

Build the tree and ask for the LCA of 4 and 7.

int main() {
    std::unique_ptr<Node> root;
    for (int v : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(std::move(root), v);
 
    int visited = 0;
    const Node* answer = generic_lca(root.get(), 4, 7, visited);
    std::cout << "generic LCA(4, 7): " << answer->value << " visited=" << visited << "\n";
}

Output:

generic LCA(4, 7): 6 visited=9

The answer is right. The search visited all nine nodes. It went into the left side of 8, found 4 and 7 there, and still went into the right side of 8 to check whether something else was there.

The fast way: the value order picks the side

The BST rule lets you decide the direction at each node. Take a node with value v and two targets p and q. There are three cases.

• If both p and q are less than v, both targets are in the left subtree. The LCA is in the left subtree too, so go left. Nothing on the right can be the answer.
• If both p and q are greater than v, both targets are in the right subtree. Go right.
• Otherwise, one target is less than or equal to v and the other is greater than or equal to v. The node v sits between them, so it is the split point. No node below v can hold both targets, so v is the lowest common ancestor. The LCA is v.

The third case includes the situation where v equals one of the targets. Then v is an ancestor of the other target, so v is the answer.

Think of a set of alphabetical folders. If both names start before "M", the shared folder must be among the "A to L" group, so you can ignore the "M to Z" group. You keep narrowing the group until a folder splits the two names. That folder is the answer.

Worked example 1: LCA of 4 and 7

Trace the search for 4 and 7 from the root.

1. At 8. Both 4 and 7 are less than 8. Go left to 3.
2. At 3. Both 4 and 7 are greater than 3. Go right to 6.
3. At 6. The value 4 is less than 6, and the value 7 is greater than 6. The node 6 splits them. The answer is 6.

The search visited three nodes, 8, 3 and 6. It never looked at the right side of 8, where 10, 14 and 13 sit. The skipped nodes did not need to be checked, because the order already shows that they cannot hold the answer.

Worked example 2: a value that is an ancestor

Now find the LCA of 3 and 6. The value 3 is an ancestor of 6, so the answer should be 3.

1. At 8. Both 3 and 6 are less than 8. Go left to 3.
2. At 3. The value 3 equals p, so node 3 is the split point. The answer is 3.

The search visited two nodes. The check p < cur->value && q < cur->value was false, and the check p > cur->value && q > cur->value was also false, so the code fell to the last branch and returned node 3.

The code below implements the walk. It uses a loop instead of recursion, so there is no stack of function calls to manage. It also counts visits, so you can compare the work with the generic version.

const Node* bst_lca(const Node* root, int p, int q, int& visited) {
    const Node* cur = root;
    while (cur != nullptr) {
        ++visited;
        if (p < cur->value && q < cur->value) {
            cur = cur->left.get();
        } else if (p > cur->value && q > cur->value) {
            cur = cur->right.get();
        } else {
            return cur;
        }
    }
    return nullptr;
}

Run both versions on the same queries.

int main() {
    std::unique_ptr<Node> root;
    for (int v : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(std::move(root), v);
 
    const std::vector<std::pair<int, int>> queries{{4, 7}, {3, 6}, {1, 13}, {13, 14}, {1, 4}, {4, 4}};
    for (auto [p, q] : queries) {
        int fast_visited = 0, slow_visited = 0;
        const Node* fast = bst_lca(root.get(), p, q, fast_visited);
        const Node* slow = generic_lca(root.get(), p, q, slow_visited);
        std::cout << "LCA(" << p << ", " << q << "): bst=" << fast->value
                  << " visited=" << fast_visited
                  << " | generic=" << slow->value << " visited=" << slow_visited << "\n";
    }
}

The program needs #include <vector> for std::vector and <utility> for std::pair. Those includes are left out of the snippet to keep it short, but add them to the top of the file before you compile.

Output:

LCA(4, 7): bst=6 visited=3 | generic=6 visited=9
LCA(3, 6): bst=3 visited=2 | generic=3 visited=5
LCA(1, 13): bst=8 visited=1 | generic=8 visited=9
LCA(13, 14): bst=14 visited=3 | generic=14 visited=8
LCA(1, 4): bst=3 visited=2 | generic=3 visited=9
LCA(4, 4): bst=4 visited=4 | generic=4 visited=9

Both versions returned the same node on every query. The BST version visited between one and four nodes. The generic version visited between five and nine.

The LCA of 1 and 13 took one visit. The root 8 splits them at once, because 1 is less than 8 and 13 is greater than 8. The search ended immediately.

Worked example 3: a chain

Insert the values 1 to 10 in order. As in the earlier lesson on sorted input, the tree becomes a chain. Each node has one right child, and the root is 1.

The walk from the root goes down the chain until it reaches the split point. For the LCA of 9 and 10, both values are greater than every node from 1 to 8, so the walk goes right at each of them and reaches 9, which is the split point.

void chain_example() {
    std::unique_ptr<Node> root;
    for (int v = 1; v <= 10; ++v) root = insert(std::move(root), v);
 
    int visited = 0;
    const Node* answer = bst_lca(root.get(), 3, 9, visited);
    std::cout << "sorted input 1..10, LCA(3, 9): " << answer->value << " visited=" << visited << "\n";
 
    visited = 0;
    answer = bst_lca(root.get(), 9, 10, visited);
    std::cout << "sorted input 1..10, LCA(9, 10): " << answer->value << " visited=" << visited << "\n";
}

Output:

sorted input 1..10, LCA(3, 9): 3 visited=3
sorted input 1..10, LCA(9, 10): 9 visited=9

The first answer is quick. The walk visits 1 and 2, where both values are greater, so it goes right. At 3, the value 3 equals p, so the walk stops there after three visits. The second answer is slow. The walk goes down one node at a time, from 1 to 9, before it reaches the split point.

The number of visits equals the depth of the split node, which is how far it sits below the root. In a balanced tree that depth is about the height of the tree. In a chain it can be as large as the number of nodes.

Worked example 4: the root is the split

Some pairs are split by the root. Take 4 and 14. The root 8 is greater than 4 and less than 14, so 8 sits between them. The walk stops at the first node it visits.

The pair 8 and 4 also gives a one-step walk. The value 8 equals the root, so the root is the split point. Both versions agree on both queries.

LCA(4, 14): bst=8 visited=1 | generic=8 visited=8
LCA(8, 4): bst=8 visited=1 | generic=8 visited=1

The generic version visited eight nodes for the first pair even though the answer is the root. It had to search the whole left side of 8 to be sure that nothing there held 14. The BST version needed one look because the order already told it that 14 is not on the left.

Why the walk is safe

The walk keeps one fact true at every step. The answer lies inside the subtree the walk is in. At the start, the subtree is the whole tree, and the answer is in it because both targets are in the tree. Each time the walk goes left, both targets are less than the current value, so every target and the answer lie in the left subtree. The same holds for going right. When the walk stops, the current node splits the targets, so no node below it can be a deeper common ancestor.

This fact is why the walk never needs to check the other side. Going right at a node tells you that nothing on the left can hold a target, so the left subtree cannot contain the answer.

Checking the walk on random trees

A single example can hide a mistake, so compare the BST version with the generic version on random trees. The check below builds 300 random trees with values from -40 to 40, picks random pairs of values that exist in each tree, and checks that the two versions agree.

#include <random>
#include <vector>
 
int random_check() {
    std::mt19937 rng(7);
    std::uniform_int_distribution<int> value_dist(-40, 40);
    int checks = 0;
    for (int round = 0; round < 300; ++round) {
        std::unique_ptr<Node> tree;
        std::vector<int> present;
        int n = std::uniform_int_distribution<int>(1, 40)(rng);
        for (int i = 0; i < n; ++i) {
            int v = value_dist(rng);
            tree = insert(std::move(tree), v);
            present.push_back(v);
        }
        for (int q = 0; q < 40; ++q) {
            int p = present[std::uniform_int_distribution<size_t>(0, present.size() - 1)(rng)];
            int r = present[std::uniform_int_distribution<size_t>(0, present.size() - 1)(rng)];
            int gv = 0, bv = 0;
            const Node* generic = generic_lca(tree.get(), p, r, gv);
            const Node* fast = bst_lca(tree.get(), p, r, bv);
            if (generic->value != fast->value) {
                std::cout << "MISMATCH\n";
                return 1;
            }
            ++checks;
        }
    }
    std::cout << "random checks passed: " << checks << "\n";
    return 0;
}

Output:

random checks passed: 12000

The random pairs are always values that are in the tree. The next section shows what goes wrong when one of them is not.

Loop or recursion

The walk can be written as a loop, as in bst_lca, or as a recursive function that calls itself on one child. Both make the same decisions. The recursive version is shorter to read.

const Node* bst_lca_recursive(const Node* node, int p, int q) {
    if (node == nullptr) return nullptr;
    if (p < node->value && q < node->value) return bst_lca_recursive(node->left.get(), p, q);
    if (p > node->value && q > node->value) return bst_lca_recursive(node->right.get(), p, q);
    return node;
}

Each recursive call uses a little memory on the call stack, which is the part of memory that holds the function calls in progress. The recursion goes as deep as the walk goes, so a tree that is a long chain uses a deep call stack. The loop keeps only one pointer and does not add a stack frame for each node. For most trees the difference does not matter. For a chain of a million nodes, the loop is the safer choice.

Common mistakes

Looking at only one target

The most common mistake is to check only p at each node. The walk then ignores q, and it stops at the wrong place. Here is a version that does that. It is wrong on purpose.

const Node* wrong_lca(const Node* root, int p) {
    const Node* cur = root;
    while (cur != nullptr) {
        if (p < cur->value) cur = cur->left.get();
        else if (p > cur->value) cur = cur->right.get();
        else return cur;
    }
    return nullptr;
}

On the tree from this lesson, the LCA of 4 and 7 should be 6. Run the wrong version with p equal to 4.

wrong version, LCA(4, 7): answer=4

The answer is 4, which is wrong. The walk went 8, then 3, then 6, then 4, and stopped at 4 because it matched p. But 4 is not an ancestor of 7. Node 7 is not below 4, so 4 cannot be the lowest common ancestor. The check for q is needed at every step.

Trusting a value that is not in the tree

The walk assumes that p and q are both in the tree. If one is missing, the walk still returns a node, and that node is not a real answer.

    int v4 = 0;
    const Node* missing = bst_lca(root.get(), 4, 99, v4);
    std::cout << "LCA(4, 99): answer=" << missing->value << " visited=" << v4 << "\n";

Output:

LCA(4, 99): answer=8 visited=1

The answer 8 looks valid, but 99 is not in the tree, so there is no LCA to find. Check that both values exist before you call the function, or have the function return a flag that says whether it found both.

Returning a pointer as an int

The function must return a pointer to the node, not the value stored in it. Returning an int causes a compile error. This version is wrong.

int bst_lca_bad(const Node* root, int p, int q) {
    const Node* cur = root;
    while (cur != nullptr) {
        if (p < cur->value && q < cur->value) cur = cur->left.get();
        else if (p > cur->value && q > cur->value) cur = cur->right.get();
        else return cur;
    }
    return nullptr;
}

Compiling it with g++ -std=c++20 -Wall gives these errors. The file and line numbers come from the test file used to check it.

mistake_lca.cpp:15:21: error: invalid conversion from 'const Node*' to 'int' [-fpermissive]
mistake_lca.cpp:17:12: error: cannot convert 'std::nullptr_t' to 'int' in return

The first error points at return cur;. The compiler is saying that cur is a pointer and the function promised an int. Change the return type to const Node* to fix both errors. If you want the value only, return cur->value in the caller, after checking that the pointer is not nullptr.

Forgetting the equal case

The third case of the rule must include values equal to v. If you write the tests as p <= cur->value and q <= cur->value, then a target equal to the current node takes the left branch, and the walk misses the node itself. Use < for the left test and > for the right test, as in the code above.

Practice

Exercise 1

Use the example tree from this lesson. Find the LCA of 13 and 14 with the BST walk. Give the answer and the number of visited nodes.

Show the answer

The answer is 14. The walk visits 8, then 10, then 14. At 8 and at 10, both values are greater, so the walk goes right. At 14, the value 13 is less than 14 and the value 14 equals the node, so 14 is the split point. The output is LCA(13, 14): 14, with 3 visited nodes.

Exercise 2

Use the example tree. Find the LCA of 1 and 4 with the BST walk. Give the answer and the number of visited nodes.

Show the answer

The answer is 3. The walk visits 8, then 3. At 8, both values are less than 8, so the walk goes left. At 3, the value 1 is less than 3 and the value 4 is greater than 3, so 3 splits them. The output is LCA(1, 4): 3, with 2 visited nodes.

Exercise 3

Use the chain of values 1 to 10, inserted in order. Find the LCA of 2 and 3. Give the answer and the number of visited nodes, and explain why the number is small.

Show the answer

The answer is 2. The walk visits 1, then 2. At 1, both values are greater, so the walk goes right. At 2, the value 2 equals the node, so 2 is the split point. The walk visits 2 nodes. The number is small because the split point is near the root.

Exercise 4

Write the same walk as a recursive function. It should return the node pointer, and it should not take a visited counter. Run it on the example tree for the pair 13 and 14, and check that it prints 14.

Show the answer

const Node* bst_lca_recursive(const Node* node, int p, int q) {
    if (node == nullptr) return nullptr;
    if (p < node->value && q < node->value) return bst_lca_recursive(node->left.get(), p, q);
    if (p > node->value && q > node->value) return bst_lca_recursive(node->right.get(), p, q);
    return node;
}

The output for 13 and 14 is recursive LCA(13, 14): 14. The recursive version makes the same decisions as the loop. It passes the search to one child, or returns the current node when the values split. Both versions visit the same nodes.

Exercise 5

Use the chain of values 1 to 10, inserted in order. Find the LCA of 7 and 8. Give the answer and the number of visited nodes, and say why the number is large.

Show the answer

The answer is 7. The walk visits 1, 2, 3, 4, 5, 6 and then 7. At each of the nodes 1 to 6, both values are greater, so the walk goes right. At 7, the value 7 equals the node, so 7 is the split point. The output is sorted input 1..10, LCA(7, 8): 7 visited=7, so the walk visits 7 nodes. The number is large because the chain makes the split point the seventh node from the root.

Summary

• The lowest common ancestor is the deepest node that is an ancestor of both targets. A node counts as its own ancestor.
• A general binary tree must search both sides. A BST uses the value order to choose one side at each node.
• The walk stops at the first node whose value is not less than both targets and not greater than both. That node is the answer.
• The walk visits the nodes from the root down to the answer, so its cost depends on how deep the answer sits.
• Check both targets at every step, and check that both values exist in the tree before you trust the answer.