Lowest common ancestor in a Python BST

Why it matters

Many questions about two items in a tree ask where their paths meet. In a company chart, the question is which manager is the closest one above two employees. In a folder tree, it is which folder holds both files. In both cases the answer is the closest shared point above the two items, and walking up from each item to the top is more work than the question needs.

A binary search tree (BST) keeps its values in order, so it can answer this question by walking down a single path. This lesson shows how the ordering removes the need to search both branches. It uses the insert and tree-walk ideas from the first lesson of this module, "BST basics, insert and search in Python". The version for any binary tree, which does not use ordering, is in the lesson "Lowest common ancestor" of the binary trees module.

By the end you will be able to find the lowest common ancestor in a BST with a loop, explain why one path is enough, and measure how many nodes the walk visits compared with a general search.

The question in plain words

An ancestor of a node is any node above it on the path to the root. The root is the ancestor of every node. For this lesson, a node also counts as its own ancestor. That choice matters when one of the two values is the answer.

The lowest common ancestor (LCA) of two values p and q is the node that is an ancestor of both and is the lowest one, meaning the closest to them. It is the deepest point where their two paths from the root meet.

The examples use the classic 9-node tree below. It is built by inserting 6, 2, 8, 0, 4, 3, 5, 7 and 9, in that order. Each line is one node, and the indentation shows which node it hangs under.

6
├── 2
│   ├── 0
│   └── 4
│       ├── 3
│       └── 5
└── 8
    ├── 7
    └── 9

Build it with the TreeNode class and insert function from the first lesson of this module. The variable classic holds its root.

classic = None
for v in [6, 2, 8, 0, 4, 3, 5, 7, 9]:
    classic = insert(classic, v)

Some answers on this tree:

• The LCA of 2 and 8 is 6. The value 2 is in the left subtree of 6, and 8 is in the right subtree. The two paths split at 6, so 6 is the lowest point they share.
• The LCA of 3 and 5 is 4. Both are under 4, and 4 is the lowest node above both.
• The LCA of 2 and 4 is 2. The value 4 is under 2, and 2 counts as its own ancestor. The lowest node above both is 2 itself.

The last example is the reason for the rule that a node is its own ancestor. Without it, the answer for 2 and 4 would have to be 6, which is not the lowest node that holds both paths.

The general method: search both branches

Before using the BST rule, look at the method that works on any binary tree. The method searches the left subtree and the right subtree of each node.

• If the node is p or q, return the node.
• Otherwise, search the left subtree and the right subtree.
• If both searches found something, the two values are on opposite sides of this node, so this node is the LCA.
• If only one search found something, pass that result up, because both values are on the same side.

A subtree is a node together with everything below it. Each child starts its own subtree. The general method needs both searches because a plain binary tree gives no hint about which side holds a value. The method must look at both sides before it can decide.

Here is the code. The visits counter counts how many nodes the method looks at, so you can compare the two methods. The function changes visits with global visits, as in the range sum lesson.

visits = 0
 
 
def lca_generic(node, p, q):
    global visits
    if node is None:
        return None
    visits += 1
    if node.val == p or node.val == q:
        return node
    left = lca_generic(node.left, p, q)
    right = lca_generic(node.right, p, q)
    if left is not None and right is not None:
        return node
    return left if left is not None else right

Read the two lines in the middle with care. Both calls always run, even when the left call has already found an answer. The function cannot know whether the right side holds the other value until it looks.

Method 2: use the BST rule

Now use the BST rule. Take the node v at the top of a search, and compare the two values p and q with v.

• If both values are smaller than v, both are in the left subtree. The LCA must be in the left subtree too, so go left. The right subtree and the node v itself cannot be the answer.
• If both values are larger than v, both are in the right subtree. Go right.
• Otherwise, one value is smaller or equal, and the other is larger or equal. The two values are on opposite sides of v, or one of them is v. Either way, v is the lowest node above both. Return v.

The third case is the one that ends the walk. It is the first node where the two paths split. Because the tree is ordered, you can tell where the split is by comparing values, without looking at the other side.

Here is the code as a loop.

def lca_bst(root, p, q):
    global visits
    node = root
    while node is not None:
        visits += 1
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node
    return None

The loop does one comparison round per node on the path, and it never goes back up. It stops at the split node, so it never needs to look at the other branch. The function returns None only when the walk runs off the tree, which happens when a value is not in the tree.

Why one path is enough

Imagine the two values are 3 and 5 on the classic tree. Both are in the tree, so the walk must end at the node where their paths split. Before that node, both values are on the same side of every node, so the walk goes that way. The first node where they are on different sides, or where one of them is the node, is the answer. No other node can be lower and still be above both values, because the walk has already gone down into the only subtree that holds both.

That is why the walk visits one path. It never has to check whether p or q happens to be in the other subtree, because the ordering already says which subtree that is.

Worked example 1: the split is deep in the tree

Use the values 3 and 5 on the classic tree. The table shows each step.

The walk visited 3 nodes. The general method would visit 9 nodes for the same pair, as the next section shows.

Worked example 2: one value is the answer

Now use the values 2 and 4. The value 2 is an ancestor of 4, so the answer should be 2.

The node 2 is equal to p, so neither "both smaller" nor "both larger" is true. The else branch returns it. This is the reason the equal case needs no special code. A value equal to the node is treated as a split, and the node is the answer.

Worked example 3: a large tree with random pairs

The classic tree is small, so the next test uses a larger one. It calls random.seed(7), draws random.randint(0, 99999) until the set holds 2000 different values, inserts them in set order, and then picks 500 random pairs with random.sample. For each pair it runs both methods and checks that they return the same node. The output of the test is:

random pairs on 2000-node tree: agree 500 of 500
total visits: bst walk 3552, generic 919373

Both methods agreed on all 500 pairs. The BST walk visited 3552 nodes in total, which is about 7.1 nodes per pair. The general method visited 919373 nodes, which is about 1839 per pair, so it looked at nearly the whole tree every time.

The reason is the pattern of the general method. A pair of values is usually deep in the tree and on different sides of the root. The general method has to search the whole side of the tree that holds the answer, and then it still searches the other side, because it cannot know the other side is empty of the second value until it looks. The BST walk never enters the side it does not need.

Comparing the two methods on the classic tree

The classic tree is small enough to show the counts for each pair. The output below is from calling lca_bst and lca_generic on each pair, with visits reset to 0 before each call. The first number is the BST walk, and the second is the general method.

LCA(2, 8) = 6   bst visits = 1, generic visits = 3, generic = 6
LCA(2, 4) = 2   bst visits = 2, generic visits = 5, generic = 2
LCA(3, 5) = 4   bst visits = 3, generic visits = 9, generic = 4
LCA(0, 5) = 2   bst visits = 2, generic visits = 9, generic = 2
LCA(4, 4) = 4   bst visits = 3, generic visits = 7, generic = 4
LCA(7, 9) = 8   bst visits = 2, generic visits = 9, generic = 8

The general method sometimes stops early. For 2 and 8 it visited 6, then 2, which is a match and returns at once, then 8, which is also a match. That is 3 visits. But for 3 and 5 it visited every node under 6 before it knew the answer was 4, and then it still searched the right side of 6, which holds 8, 7 and 9. That is 9 visits, the whole tree. The BST walk gives the same answer in 3 visits, because the ordering tells it which side to take at each step.

The lesson here is not that the general method is wrong. It is correct on any binary tree. The BST walk is correct on a BST and uses the ordering to avoid the searches the general method must do.

The recursive version

The same walk can be written as a recursive function. The idea does not change: go down one side, or stop at the split. Recursion means a function that calls itself on a smaller part of the problem.

def lca_bst_rec(node, p, q):
    global visits
    if node is None:
        return None
    visits += 1
    if p < node.val and q < node.val:
        return lca_bst_rec(node.left, p, q)
    if p > node.val and q > node.val:
        return lca_bst_rec(node.right, p, q)
    return node

Both versions visit the same nodes. The loop version uses constant extra memory, because it reuses one variable. The recursive version uses one stack frame per level of the tree, which is a block of memory the program keeps while a call is waiting. On a balanced tree that is a few frames, but on a long chain it can be as many frames as the tree has levels. Python stops a call chain at about 1000 calls by default, so a chain of that length fails with RecursionError. For a tree that could be a long chain, the loop is the safer choice, and the recursive form is easier to read at first.

Common mistakes

Mistake 1: using or instead of and

The most common error is to change one and to or in the first condition. Here is a version with that change.

# Wrong: or instead of and.
def lca_buggy(root, p, q):
    node = root
    while node is not None:
        if p < node.val or q < node.val:
            node = node.left
        elif p > node.val or q > node.val:
            node = node.right
        else:
            return node
    return None
 
 
print(lca_buggy(classic, 2, 8))

The change looks small, and it breaks the logic. With or, the walk goes left as soon as one value is smaller, even if the other is larger. For 2 and 8 the buggy walk goes left at 6, right at 2 (because 8 is larger), left at 4 (because 2 is smaller), and left at 3, where there is no child. It returns None, and the program prints:

None

If the caller then reads an attribute of that result, Python stops with this message:

AttributeError: 'NoneType' object has no attribute 'val'

The fix is to use and in both conditions. Both values must be smaller before the walk goes left, and both must be larger before it goes right.

Mistake 2: a value that is not in the tree

The BST walk assumes both values are in the tree. If one is missing, the walk still returns a node, and the node can look right. Here is the classic tree with the value 1, which is not in it, and the value 4.

print("missing 1:", lca_bst(classic, 1, 4).val, lca_generic(classic, 1, 4).val)

missing 1: 2 4

The walk returned 2. That looks plausible, because 2 is an ancestor of 4. But 1 is not in the tree, so the answer does not mean anything. The general method returned 4, which is also not a meaningful answer. Neither method reports the problem. If the input can contain values that are not in the tree, check membership first with the search from the first lesson of this module.

Mistake 3: an empty tree

When the root is None, the walk returns None at once. Code that reads an attribute of that result fails. Here is the walk called on an empty tree, and a line that reads the answer's value.

a = lca_bst(None, 1, 2)
print(a.val)

The program stops with this message:

AttributeError: 'NoneType' object has no attribute 'val'

The fix is to check for None before reading the field, or to make sure the tree is not empty when the question is asked.

Mistake 4: searching both branches in a BST

The general method is correct on a BST too, so it is tempting to use it and skip the ordering. It gives the same answers, as the random test showed. But it visited about 259 times as many nodes on the 2000-node tree, because it searches both sides. On a tree with a million nodes, that difference becomes a large cost. The BST walk is the right tool when the tree is a BST, and the general method is the right tool when the tree is not ordered.

Practice

Each exercise has its answer below it. Try the exercise on paper first, using the classic 9-node tree.

Exercise 1: the answer is on the left

Find the LCA of 0 and 4 with the BST walk. Give the nodes visited in order.

Show the answer

The LCA is 2, and the walk visits 6, then 2. At 6, both values are smaller, so the walk goes left to 2. At 2, the value 0 is smaller and the value 4 is larger, so the two values split here.

Exercise 2: the answer is the root

Find the LCA of 6 and 9 with the BST walk. Give the number of visited nodes.

Show the answer

The LCA is 6, and the walk visits 1 node. At 6, the value 6 is not smaller than 6, so the first condition fails. The value 9 is larger than 6, but the value 6 is not larger than 6, so the second condition fails too. The else branch returns 6.

Exercise 3: both values on the right

Find the LCA of 5 and 9 with the BST walk. Then write down the general method's visit count for the same pair, based on the rule that it searches both sides.

Show the answer

The LCA is 6. At 6, the value 5 is smaller and the value 9 is larger, so the values split at the root, and the BST walk returns 6 after one visit. The general method also returns 6, but it only knows that after it has searched both sides of 6. It visits all 9 nodes of the tree, which is 9 visits.

Exercise 4: the same node, twice

What does the BST walk return for the pair 4 and 4, and why? Count the visits.

Show the answer

It returns 4. The walk goes from 6 to the left, because both values (4 and 4) are smaller than 6. At 2, both values are larger than 2, so it goes right to 4. At 4, both values equal the node, so neither "both smaller" nor "both larger" is true, and the else branch returns 4. The walk visits 3 nodes, as the output in the lesson shows.

Exercise 5: write the right-side version

Write the recursive version of the walk so that it moves to the right child when both values are larger than the node, and to the left child when both are smaller. Then state what it returns for the pair 7 and 9.

Show the answer

The function is the same as lca_bst_rec in the recursive version section. For 7 and 9, the walk starts at 6. Both values are larger than 6, so it goes right to 8. At 8, 7 is smaller and 9 is larger, so the values split at 8, and the function returns 8.

Summary

• The lowest common ancestor of two values is the lowest node that lies above both of them, and a node counts as its own ancestor.
• The general method searches both subtrees of each node. It works on any binary tree and visits many nodes in a BST.
• In a BST, compare both values with the current node. If both are smaller, go left. If both are larger, go right. Otherwise, the node is the LCA.
• The BST walk visits one path, so it stays short on a balanced tree and stops at the split node.
• Check that both values are in the tree before you trust the answer, and use and in both conditions.