Distance Between Two Nodes in a BST

Distance Between Two Nodes in a BST asks for the number of edges on the shortest path between two values. The trick is to lean on the BST ordering: the path between two nodes always bends at one special node — their split point.

The slow way first

You could find the full root-to-p path and the full root-to-q path as lists, then walk both from the front until they stop agreeing, and add up the remaining lengths. That works, but it stores two whole paths and does extra bookkeeping.

The question to ask: where does the path between p and q actually turn? It turns at exactly one node — the lowest node that has p in one subtree and q in the other. That is the lowest common ancestor (LCA), and in a BST we can find it without storing any paths.

The idea: split point, then count down

In a BST, walking down from the root, both targets go the same direction as long as they are on the same side of the current node. The first node where they go different directions (or where the node equals one of them) is the split point — the LCA. From there, the distance is just the depth down to p plus the depth down to q.

The key insight: because it is a BST, every comparison tells us which way to go in O(1), so both the LCA search and the two depth counts are simple while-loops.

Walk through it

Step through the animation. From root 6, both 1 and 5 are smaller, so we go left to 3. At 3 they split — 1 < 3 but 5 > 3 — so 3 is the LCA. Then we count edges down: 3 → 1 is 1 edge, and 3 → 4 → 5 is 2 edges. The distance is 1 + 2 = 3.

Pseudocode

lca = root
while lca is not None:
    if both p and q are less than lca.val:  go left
    elif both p and q are greater:          go right
    else:                                    stop -- this is the split point
for each target value (p, then q):
    walk down from lca, counting edges until you reach the value
return depth_to_p + depth_to_q

The Python solution

def distance(root, p, q):
    # 1. find the split point (lowest common ancestor)
    lca = root
    while lca:
        if p < lca.val and q < lca.val:
            lca = lca.left
        elif p > lca.val and q > lca.val:
            lca = lca.right
        else:
            break
    # 2. count edges from the lca down to each value
    def depth(node, val):
        d = 0
        while node.val != val:
            node = node.left if val < node.val else node.right
            d += 1
        return d
    return depth(lca, p) + depth(lca, q)

• lca starts at the root and walks down following BST order.
• If both p and q are smaller than the current node, both live left, so we move left; if both are bigger, we move right.
• The first time they are not both on the same side, we break — that node is the split point.
• depth(node, val) walks straight down from a node to val, counting one edge per step. The BST order tells it whether to go left or right each time.
• The answer is depth(lca, p) + depth(lca, q) — the two arms of the path joined at the LCA.

Complexity

Every step moves strictly downward, so the total work is bounded by the tree height h. For a balanced BST that is O(log n); in the worst case (a degenerate, list-like tree) it is O(n). We use only a couple of variables, so the extra space is O(1).

When this pattern shows up

Practice