Lowest common ancestor in Python

Why this lesson matters

"Where do two paths meet?" is one of the most common questions in tree work. In a file system, it asks for the nearest folder that contains two files. In an organisation chart, it asks for the nearest manager who oversees two employees. In a version control system such as Git, it asks for the most recent commit that two branches share, which is the point where their histories split. Each of these is a question about two nodes and the path that joins them to the root. The answer is the lowest node that sits above both.

This lesson teaches the recursive method for the answer, which is short and works on any binary tree. You will then handle the case where one of the two values is missing, which the first version ignores. You will also see a second method that stores each node's parent in a dictionary, which is easier to explain to someone else and works well when you have to answer many questions about the same tree. Finally, you will use the answer to compute the distance between two nodes, which is a number that shows up in network routing, game maps and genealogy.

This lesson uses the same tree class as the first lesson, and the recursion and None checks from the lessons before it. Everything else is introduced below.

The idea: ancestors and the lowest one

An ancestor of a node is any node on the path from the root down to that node. Every node is its own ancestor, which is the rule that makes the rest of this lesson work. The root is an ancestor of every node. A node's parent is its closest ancestor, and a node's grandparent is the ancestor two steps up.

The lowest common ancestor, written LCA, of two nodes p and q is the deepest node that is an ancestor of both. "Lowest" means closest to the two nodes, not closest to the root. Think of two cousins in a family tree. Their parents are siblings, so the two cousins have different parents. Their nearest shared ancestor is the grandparent that their parents both had. That grandparent is the LCA of the two cousins, because no one lower in the tree is above both of them.

Here is the six-node tree from the first lesson, which we will use in most examples:

        1
       / \
      2   3
     / \   \
    4   5   6

Here are a few LCA questions, each answered in plain words first.

• The LCA of 4 and 5 is 2. Both sit under 2, and no lower node holds both. Node 2 is the lowest one.
• The LCA of 4 and 6 is 1. Node 4 is under 2, and node 6 is under 3. The only node above both is the root.
• The LCA of 2 and 4 is 2. Node 2 is an ancestor of 4, and node 2 is also an ancestor of itself. Because each node is its own ancestor, the LCA of a node and one of its own descendants is that node.
• The LCA of 5 and 3 is 1. Node 5 sits under 2, and node 3 is the other child of the root.

The last two rules are the ones beginners forget. A node counts as its own ancestor. A node that is an ancestor of the other value is the answer, even though it is one of the two values.

The recursive idea

The recursive function asks a simple question of each subtree: "does this subtree contain p, or q, or both?" The answer is returned as a node. If a subtree contains one of the values, it returns that value's node. If it contains neither, it returns None. If it contains both, the node where they split is the answer.

The algorithm, in plain steps:

1. If the current node is None, return None, because an empty subtree holds neither value.
2. If the current node holds p or q, return the current node. It is one of the two values, and the other value, if it exists, is below it or somewhere else. Either way, this node is the answer for this subtree.
3. Otherwise, search the left subtree and the right subtree.
4. If both searches return a node, one value was found on each side. The current node is where the paths split, so it is the LCA. Return it.
5. If only one search returns a node, both values are on that side, or only one exists. Pass that node upward.
6. If neither search returns a node, return None.

The key observation is step 4. A node returns a real node only if its subtree holds at least one of the two values. If both children return a node, the two values must lie in different subtrees, and no node below the current one can hold both. The current node is therefore the lowest one above both.

The code is short. Here it is, with a block at the bottom that checks the three examples from the start of the lesson. The type hints after the colons, such as TreeNode | None, say what each value can be. Python does not check them when the code runs, but they make the code easier to read and let an editor warn you about mistakes.

Output:

LCA of 4 and 5: 2
LCA of 4 and 6: 1
LCA of 2 and 4: 2

The function returns a TreeNode, not a number, so the code reads .val to show the value of the node that comes back. This works because all three values exist in the tree. The next section handles the case where one does not.

The line return left if left is not None else right is a conditional expression. It reads as "return left if it is set, otherwise return right". It does the same job as an if statement with two return lines.

Trace the call for LCA of 4 and 6

Tracing a recursive function is the surest way to understand it. Here is the call lca(1, 4, 6), step by step. Each row shows one call, what it returns, and why.

The last row is the important one. Node 1 receives a node from its left side, which holds 4, and a node from its right side, which holds 6. Both values are in different subtrees, so 1 is the lowest node above both.

The call stack for these calls looks the same as in the earlier lessons. The frames go down toward 4 and 6, then return their answers up.

Picture the two paths from the root. The path to 4 is 1, 2, 4. The path to 6 is 1, 3, 6. They share only the root, so the root is the LCA. For the LCA of 4 and 5, the paths are 1, 2, 4 and 1, 2, 5. They share node 2 before they separate, and 2 is the answer.

Why the function returns early

Look at this part of the function: if node.val == p or node.val == q: return node. It returns immediately when the current node holds one of the values, without searching the subtree below it. A beginner often asks whether that misses the other value.

It does not, and the reason is worth understanding. Suppose the current node is 2, and we are looking for p = 2 and q = 4. Node 4 is below node 2. If the function returns 2 at once, it has correctly reported that 2 is an ancestor of 4 and that 2 is the lowest such node. Any node below 2 that could be the answer would have to hold both 2 and 4, but 2 is the node itself, so nothing below it can be an ancestor of 2. The early return is correct, and it saves work.

A similar argument covers the case where the other value is in the other subtree. If the function returns the node holding p, and q is somewhere else in the tree, the caller on the other side of the split will find q and return its node. The split is then found one level up, at the lowest common node, which is what we want.

What happens when a value is missing

The function above assumes that both p and q exist in the tree. If one is missing, the function still returns something, but the answer is wrong. Look at the call lca(root, 4, 9). Node 9 is not in the tree, so only 4 is ever found. Node 4 returns 4 up its side, and the other side returns None. The function then returns 4, which looks like a valid answer but means nothing, because 9 is not in the tree.

To fix this, check that both values exist before you run the LCA. A helper function called contains searches the tree for a value and returns True or False. The next program uses it to print missing when either value is absent.

Output:

4 and 5: 2
4 and 9: missing
9 and 9: missing

The contains check runs first, so lca is only called when both values are in the tree. The contains function uses the same recursion as before, with its own base case. It returns False for None, and it returns True as soon as it finds the value. The or in its last line is short-circuiting. Python stops at the first part that is true, so the right subtree is not searched once the left one has found the value.

The cost is one extra search for each value, so the total time is still O(n), with a constant of about three passes instead of one. In most programs this is fine. If you need many queries on the same tree, the parent dictionary below is faster per query.

Complexity of the recursive method

The function visits each node at most once, and each visit does a fixed amount of work. So the time is O(n). The space is the call stack, which holds one frame per node on the path from the root to the current node. That is O(h), where h is the height. For a balanced tree that is about log n, and for a chain it is n.

Notice that the function does not always visit every node. It skips the subtree below any node that matches one of the values. The O(n) bound is the worst case, which happens when the two values are deep in the tree or when one of them is missing.

An alternative: store each node's parent

Some programs answer many LCA questions on the same tree. Running the recursion each time is wasteful, because the tree does not change between questions. The alternative is to visit the tree once, store the parent of each node in a dictionary, and answer each question by walking up from the two nodes.

The method has three steps.

1. Walk the tree once, level by level. For each child, store its parent's value in a dictionary.
2. For the first value p, walk up the parent dictionary to the root, and store every value you pass in a set. The set holds all ancestors of p, including p itself.
3. For the second value q, walk up the parent dictionary. The first value you meet that is in the set is the LCA.

A dictionary is Python's key and value store. parent_of[4] = 2 stores the key 4 with the value 2. parent_of.get(4) reads it, and returns None when the key is missing instead of raising an error. A set is a collection with no repeats, which can answer "is this value in here?" quickly.

The next program does this. It builds the dictionary with a breadth-first walk, which you know from the third lesson, and it answers the same three questions.

Output:

4 and 5: 2
4 and 6: 1
2 and 4: 2
4 and 9: None

The root has no entry in parent_of, so the walk up stops there. This is why the loops test cur is not None. The last line prints None because 9 has no parent entry, so the walk up from 9 would stop at once. Compare the output with the earlier missing message. The dictionary version returns None when a value is absent, and the code that calls it must decide what that means. The function is correct for 4 and 9 in the sense that no node is their ancestor, and it is safe because the walk never loops.

The line parent_of.clear() empties the dictionary before the new tree is read. Without it, a parent entry from an earlier tree could stay in the dictionary and give a wrong answer for a value that is in the new tree but has a different parent.

The cost of building the dictionary is O(n). Each question then takes O(h) time, because the walk up goes no further than the height. The dictionary uses O(n) extra space, which is the price for answering questions faster.

The distance between two nodes

The distance between two nodes is the number of edges on the path between them. The path goes up from one node to the LCA, then down to the other node. If the depth of p is the number of edges from the root to p, and the same for q, then the path from p to q has this length:

distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA)

The formula subtracts twice the LCA's depth, because the path from the root to the LCA is counted in both depths, and the distance must not include it twice. Think of two people who walk from a shared meeting point, each going to their own house. The distance between the houses is the two walks added together, without the shared part that the walks cover twice.

Here is the formula in code. It uses the recursive LCA and a depth function. The depth of the root is 0, and each step down adds 1. The function returns -1 when a value is not in the tree. The d=0 in the depth definition is a default argument: when the caller does not pass d, Python uses 0.

Output:

distance 4 to 6: 4
distance 4 to 5: 2
distance 2 to 4: 1
distance 4 to 9: -1

Check the first line by hand. Node 4 has depth 2, node 6 has depth 2, and the LCA is 1 with depth 0. The distance is 2 + 2 - 2 * 0, which is 4. The path 4, 2, 1, 3, 6 has four edges, which matches. For 4 and 5, the LCA is 2 with depth 1, so the distance is 2 + 2 - 2 * 1, which is 2. The path 4, 2, 5 has two edges.

The check for missing values comes first. Without it, lca could return the node of the value that exists, and the formula would give a number that means nothing. The check makes the function safe to use.

Common mistakes and the errors they cause

Returning the left result when both sides are nodes

The most common mistake is to write the split test as if left is not None: return left before the check for both sides. That returns the left answer and ignores the right side. For the call lca(root, 4, 6), it would return 4 instead of 1, which is the child rather than the split point. The fix is to test for both sides first, as the working code does.

Forgetting that a node is its own ancestor

If the function searches below a node that holds p before it returns, it can miss the case where the other value is also below p. Returning at once when the value matches is the correct behaviour, because a node counts as its own ancestor. Test the LCA of a node and one of its descendants, such as 2 and 4, to make sure you return 2.

Reading .val from a None result

The call lca(root, 4, 9).val looks reasonable, but lca returns None when the values are not in the tree. Python then stops with an AttributeError. Here is the message from calling .val on a None result. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def lca(node, p, q):
    if node is None:
        return None
    if node.val == p or node.val == q:
        return node
    left = lca(node.left, p, q)
    right = lca(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
 
 
root = TreeNode(1)
print(lca(root, 8, 9).val)

The output is:

Traceback (most recent call last):
  File "main.py", line 21, in <module>
    print(lca(root, 8, 9).val)
          ^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The message names the type that did not have the attribute, NoneType, which is what lca returned. The last line of the traceback shows the call in your own code. Check the result for None before you read .val, or use the safe_lca pattern from this lesson so that the missing case is handled first.

Comparing a node with a number

The function compares node.val with p, which is a number. A tempting mistake is to compare the node itself with the number, as in node == p. Java refuses that comparison at compile time. Python does not. It accepts the comparison, and the answer is always False, because a TreeNode is never equal to a number. The function then never finds a match, and the mistake shows up later, when the code reads .val from a None result. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def lca_wrong(node, p, q):
    if node is None:
        return None
    if node == p or node == q:
        return node
    left = lca_wrong(node.left, p, q)
    right = lca_wrong(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
 
 
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(lca_wrong(root, 4, 5).val)

The output is:

Traceback (most recent call last):
  File "main.py", line 26, in <module>
    print(lca_wrong(root, 4, 5).val)
          ^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The error points at .val, not at the comparison that caused it. This is a silent bug, and it is the reason to write node.val == p and not node == p. Read the code for each comparison and ask what each side is. The fix is to compare the value, because val is a number and p is a number.

Reading a field before the None check

If the function reads node.val before it checks node is None, the first None child crashes the program. The message points at the attribute, not at the variable, so you need to read the line to see which object was None.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def lca_unchecked(node, p, q):
    if node.val == p or node.val == q:
        return node
    left = lca_unchecked(node.left, p, q)
    right = lca_unchecked(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
 
 
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(4)
print(lca_unchecked(root, 4, 9).val)

The output is:

Traceback (most recent call last):
  File "main.py", line 21, in <module>
    print(lca_unchecked(root, 4, 9).val)
          ~~~~~~~~~~~~~^^^^^^^^^^^^
  File "main.py", line 11, in lca_unchecked
    left = lca_unchecked(node.left, p, q)
  File "main.py", line 12, in lca_unchecked
    right = lca_unchecked(node.right, p, q)
  File "main.py", line 9, in lca_unchecked
    if node.val == p or node.val == q:
       ^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The traceback shows the line that read the field, node.val, and the call that was running at that moment. Node 2 has no right child, so the call on node 2 asks for None as its right child. The first line of that call reads None.val, and the crash happens there. The fix is to put the None check on the first line of the function, before any attribute is read.

Using the answer for a value that is missing

As shown in the section on missing values, a value that is not in the tree gives an answer that means nothing. The fix is to check existence before the LCA, or to test the result of the dictionary version for None.

Debugging walkthrough: the LCA is one level too high

Suppose your code returns 1 for the LCA of 4 and 5, but the answer should be 2. Node 1 is the root and is too high. The split test fired at the root when it should not have. The split test needs both sides to return a node. A common typo is or in place of and, which fires as soon as one side returns a node. With or, this call returns 1, because node 2 returns itself and the root sees a node on its left side only.

Check the line where the split test is. It should test left is not None and right is not None, not or. Add a print like print("at", node.val, "left", left, "right", right) before that test, run the program, and read the lines for nodes 2 and 1. The output shows which side returned what. Remove the print when you are done.

Worked example: tree M and four questions

Tree M from the second lesson is a good test for the LCA, because its two sides are deep and the paths split at different heights. Here it is again, with its values.

            1
           / \
          2   9
         / \
        3   6
       /     \
      4       7
     /         \
    5           8

Predict each answer before you read on. Node 2 is an ancestor of every node on its left and right sides, so the LCA of two nodes that sit on different sides of 2 is 2 or higher.

• The LCA of 5 and 8 is 2. Node 5 is on the left branch under 3 and 4, and node 8 is on the right branch under 6 and 7. The two paths meet at 2, and no lower node holds both.
• The LCA of 3 and 6 is 2. Node 3 is the left child of 2, and node 6 is the right child of 2. Their paths split at 2 itself.
• The LCA of 4 and 9 is 1. Node 4 is under 2, and node 9 is the right child of the root. Only the root is above both.
• The LCA of 2 and 5 is 2. Node 2 is an ancestor of node 5, and a node is its own ancestor, so the answer is the upper node.

Now trace the call lca(1, 5, 8), which must return 2. The table shows the calls that return a node. Calls that match nothing and return None are left out, because they do not change the answer.

The row for node 2 is the key row. Its two children returned 5 and 8, which were found in different subtrees, so node 2 is the lowest node above both. Node 1 then receives a node only from its left side, so it passes 2 up, and 2 is the final answer.

The same method works on the other three questions, and each one has a split point at a different height. The function never needs to know the depths in advance. It finds the split by the rule that a node returns a result only when its subtree holds one of the two values.

Why the function is correct

A short argument shows why the rule is enough. Claim: for any node, if its subtree holds both values, the call returns the lowest node above both of them. If the subtree holds only one value, the call returns that value's node. If it holds neither, the call returns None.

Check the claim on a leaf. A leaf returns its own node if it holds p or q, and None otherwise. Both results are correct, because the leaf's subtree holds only itself.

Now take a node that is not a match, and assume the claim holds for its two children. If both children return a node, then one value lies in the left subtree and the other in the right subtree. No node below the current one holds both, so the current node is the lowest common ancestor. The function returns it, which is correct. If only one child returns a node, then the subtree holds only that value, or the other value is absent. Passing the node up is correct in both cases. If neither child returns a node, the subtree holds neither value, and None is correct.

The claim holds at every node by induction, from the leaves up to the root. That is why one pass is enough.

Interview-style questions

Find the LCA of two nodes in a binary tree. Use the recursive function. Return None for an empty subtree, return the node when it matches either value, and return the node when both sides are nodes. O(n) time and O(h) space.

What if the values might be missing? Check that both values exist first, with a search that returns a boolean, or return None and let the caller decide. Mention that the recursive function alone cannot tell the difference between a missing value and a value found on one side only.

Answer many LCA queries on the same tree. Build a parent dictionary once in O(n), then answer each query by walking up from both nodes in O(h). This is the right choice when the number of queries is large.

What is the distance between two nodes? Use depth(p) + depth(q) - 2 * depth(LCA). The depths come from one walk each, and the LCA comes from the recursion. O(n) time.

How does this change for a binary search tree? The tree is ordered, so you can find the split point by comparing values. If both values are smaller than the current node, go left. If both are larger, go right. Otherwise the current node is the LCA. That method takes O(h) time without searching the whole tree. The next module on binary search trees explains why.

Real-world uses

The LCA appears wherever a tree records how things are related. A file system's path is a chain from the root folder down to a file. The LCA of two files is the deepest folder that contains both, which is the folder a program would use as a common base path when it copies files or computes a relative path. In version control, every commit points back to its parent commits, which forms a tree or a graph. Finding the LCA of two branches finds the commit where they diverged, which is the basis of a three-way merge. A company's reporting structure is a tree, and the LCA of two employees is the first manager who has authority over both, which is the natural person to approve a decision that involves both. Each of these is one question with one answer: how far up do you have to go before the two paths join?

Practice

Try each exercise on paper first, then check it with code. The answers are hidden until you open them.

1. Find the LCA of 5 and 6 in the six-node tree by hand. Then predict the answer for the LCA of 6 and 3, and explain why your answer is correct in one sentence.

Show the answer

The LCA of 5 and 6 is 1. Node 5 is under 2, and node 6 is under 3. Nodes 2 and 3 are the children of the root, so the only node above both is the root. The LCA of 6 and 3 is 3, because 3 is an ancestor of 6 and 3 is an ancestor of itself. The lowest node above both is 3 itself.

2. Write def lca_value(root, p, q): that returns the value of the LCA, or -1 when either value is missing. Test it on the six-node tree with the pairs (4, 5), (4, 6) and (4, 9). Expected output: 2, 1, -1.

Show the answer

def lca_value(root, p, q):
    if not contains(root, p) or not contains(root, q):
        return -1
    return lca(root, p, q).val

This uses contains and lca from the lesson. On the six-node tree the three calls return 2, 1 and -1. The check for missing values comes first, so the LCA function is only called when both values exist.

3. Write def is_ancestor(root, a, b): that returns True when a is an ancestor of b. Hint: a is an ancestor of b when the LCA of a and b is a. Predict the answer for (2, 4), then for (2, 6).

Show the answer

def is_ancestor(root, a, b):
    if not contains(root, a) or not contains(root, b):
        return False
    return lca(root, a, b).val == a

For (2, 4) the answer is True, because the LCA of 2 and 4 is 2. For (2, 6) the answer is False, because the LCA of 2 and 6 is 1. Node 2 is not above node 6, since 6 sits under 3.

4. Write a function count_path_nodes(root, p, q) that returns the number of nodes on the path between p and q, including both ends. Predict the answer for (4, 6). Hint: the distance is one less than this count.

Show the answer

def count_path_nodes(root, p, q):
    d = distance(root, p, q)
    return -1 if d == -1 else d + 1

The distance function is from the lesson. For (4, 6) the distance is 4, so the count of nodes on the path is 5. The path 4, 2, 1, 3, 6 has five nodes, including both ends.

5. Modify the parent-dictionary method so that it returns the list of ancestors of a value, from the value up to the root. Predict the list for node 4 in the six-node tree: [4, 2, 1].

Show the answer

Start at the value and repeatedly look up its parent, adding each value to a list until the parent is missing.

def ancestors_of(value):
    result = []
    cur = value
    while cur is not None:
        result.append(cur)
        cur = parent_of.get(cur)
    return result

For node 4 the list is [4, 2, 1]. The root's entry is absent from the dictionary, so get returns None and the loop stops after adding 1. The same loop is used inside lca_by_parents, so the code can be reused.

6. Explain in your own words why the recursive LCA returns a node at once when it finds p, even if q is below p. Use the example of the LCA of 2 and 4.

Show the answer

Node 2 is an ancestor of node 4, and each node counts as its own ancestor. Once lca finds 2 as one of the two values, the lowest common ancestor must be at or above node 2, and it cannot be lower, because nothing below 2 is an ancestor of 2. So the function returns 2 at once. Searching the subtree of 2 would find 4 and return it, which would give the wrong answer if the code took that route.

7. Write def lca_of_three(root, a, b, c): that returns the LCA of three values, or None if any value is missing. Hint: the LCA of three nodes is the LCA of the first two, combined with the third. Predict the answer for (4, 5, 6) (answer: 1).

Show the answer

def lca_of_three(root, a, b, c):
    if not contains(root, a) or not contains(root, b) or not contains(root, c):
        return None
    ab = lca(root, a, b)
    return lca(root, ab.val, c).val

For (4, 5, 6) the LCA of 4 and 5 is 2. The LCA of 2 and 6 is 1, so the answer is 1. The answer is the lowest node above all three, which is found by combining two pairwise answers.

8. A tree has values that are not unique: two nodes hold the value 4. Explain why the recursive method may give the wrong answer, and what you would need to change to make it correct.

Show the answer

The recursive method matches a node by its value, so if two nodes hold 4, it may return the wrong one, or treat the match as the value that is in the other subtree. To fix it, pass the node objects themselves, or give each node a unique id, and match on the id instead of the value. Comparing nodes with is checks that they are the same object, which is the test you want here. The parent dictionary also depends on unique values, because it stores parents by value, so a second node with the same value would overwrite the first entry.

9. Write a function that returns the depth of the LCA of two values in the six-node tree. Predict the depth for (4, 5) (answer: 1) and for (4, 6) (answer: 0).

Show the answer

def lca_depth(root, p, q):
    if not contains(root, p) or not contains(root, q):
        return -1
    a = lca(root, p, q)
    return depth(root, a.val)

For (4, 5) the LCA is 2, whose depth is 1. For (4, 6) the LCA is 1, whose depth is 0. The depth of a node is the number of edges from the root down to it.

10. Using the parent dictionary from this lesson, count the number of ancestors of node 6, not counting 6 itself. Predict the answer (2: nodes 3 and 1).

Show the answer

Walk up from 6 with parent_of. The first parent is 3, and the second is 1. The root has no parent, so the walk stops. The answer is 2 ancestors, which are nodes 3 and 1. Count the steps in the walk, not the nodes in the tree.

11. Write a program that reads a tree in the usual input format, then reads Q queries and prints the LCA of each pair, or missing. Test it with the input 7, 1 2 3 4 5 null 6, then 2, 4 5 and 5 3. Expected output: 2 and 1.

Show the answer

Use the builder from the first lesson to build the tree from the first tokens. Read Q from the next token, then read Q pairs of values. For each pair, check contains for both values and print missing if one is absent, otherwise print the LCA value. Read all the input at once with sys.stdin.read().split(), and keep a position counter that moves past each value you use. With the input 2, 4 5, 5 3, the output is 2 and 1.

12. Explain how the distance formula changes if the tree is a single chain of five nodes, and compute the distance between the top node and the bottom node. Then explain why the formula still works when the LCA is one of the two nodes.

Show the answer

A chain of five nodes is a single line of nodes, with each node one step below the one above. The top node has depth 0, and the bottom node has depth 4. The LCA of the two ends is the top node, because it is the only node above both. The distance is 4 + 0 - 2 * 0, which is 4. The formula still works when one node is the LCA, because the LCA's depth is then the depth of one of the two values. For example, the distance between a node and its own grandchild is d + (d + 2) - 2 * d, which equals 2. The subtraction removes the shared path twice, so no edge is counted twice.

What you now know

• The lowest common ancestor of two nodes is the deepest node that is above both. A node counts as its own ancestor.
• The recursive function returns the node when it finds one value and passes up a node from one side. When both sides return a node, the current node is the LCA.
• The recursive function gives a wrong answer when one value is missing, so check that both values exist first.
• A parent dictionary built once with a breadth-first walk answers each LCA question by walking up from the two nodes.
• The distance between two nodes is depth(p) + depth(q) - 2 * depth(LCA).
• The recursive function takes O(n) time and O(h) space, and the parent dictionary takes O(n) space to answer each question in O(h) time.