Start learning free

LESSON 340 OF 438 · BINARY TREES

Lowest Common Ancestor in a BST in Python: O(h) Iterative Walk

Practice O(n) Read the full explanation

Given the root of a binary search tree (BST) and two values p and q that are both in the tree, return the value of their lowest common ancestor.

The lowest common ancestor of p and q is the deepest node that has both of them in its subtree. A node counts as its own ancestor: if the node holding p is above the node holding q, the answer is p.

In a BST, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

The trees below are written in level order (top to bottom, left to right), with None for a missing child.

Example 1:

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

Input: root = [6,2,8,0,4,7,9,None,None,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the left subtree of 6 and 8 is in its right subtree, so 6 is the deepest node that has both below it.

Example 2:

Input: root = [6,2,8,0,4,7,9,None,None,3,5], p = 2, q = 4
Output: 2
Explanation: 4 is in the subtree of 2, and a node counts as its own ancestor.

Example 3:

Input: root = [6,2,8,0,4,7,9,None,None,3,5], p = 5, q = 3
Output: 4
Explanation: 3 and 5 are the two children of 4, one on each side.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
Each node value is between -10⁴ and 10⁴, and all values are different.
p and q are both values of nodes in the tree. They can be equal.

Follow up: Can you find it in O(h) time, where h is the height of the tree, using only O(1) extra space?

STEP 1 OF 6

Guided

Ctrl + Enter to check

PYTHON · BINARY TREES

Lca In Bst in Python, explained

Problem overview

The method lowestCommonAncestor receives the root of a binary search tree and two values, p and q, that both occur in the tree. It returns the value of their lowest common ancestor: the deepest node that has both values in its subtree. A node counts as its own ancestor, so if one value sits above the other, the answer is the upper one. The two values can also be equal.

In the example tree, with root 6, children 2 and 8, then 0, 4, 7 and 9 below them, and 3 and 5 under 4:

p = 2, q = 8 gives 6, because 2 is on the left of 6 and 8 is on the right.
p = 2, q = 4 gives 2, because 4 is inside the subtree of 2.
p = 5, q = 3 gives 4, because they are the two children of 4.

The follow-up asks for O(h) time, where h is the height of the tree, with O(1) extra space. This article's code does that.

Approach: follow the values down

For a general binary tree you would have to search both subtrees. A BST gives more information: at any node, every value smaller than the node's value is in its left subtree, and every larger value is in its right subtree. That lets the values themselves choose the direction.

Start at the root, which is always a common ancestor. Then ask where p and q are relative to the current node:

Both smaller than the node: both are in the left subtree, so the lowest common ancestor is there as well. Move left.
Both larger: the mirror case. Move right.
Otherwise, they are on different sides, or one of them equals the node's value. Going either way would leave one of them behind, so this node is the deepest one that has both. Return it.

The walk never goes back up and never looks at two branches, so each pass goes one level down. It makes at most h passes and needs no stack, which is why no recursion is used.

On the example with p = 5 and q = 3: at 6 both are smaller, so go left to 2. At 2 both are larger, so go right to 4. At 4, the value 5 is larger and 3 is smaller, so the answer is 4.

Step by step

Create node and set it to root. It is the node the walk is currently at.
Loop while node is not None. Each pass looks at one node and either returns or moves one level down.
Both values smaller than node.val: set node to node.left.
Both values larger: set node to node.right, using elif so only one branch runs.
Anything else: return node.val. This covers the split case and the case where p or q equals the current node.
Return -1 after the loop. Both values are in the tree, so the loop always returns earlier and this line is never reached. It only makes the function return a number on every path.

The solution in Python

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: int, q: int) -> int:
        node = root
        while node:
            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.val
        return -1

The Python details worth a closer look:

p and q are numbers, not nodes. The method compares them to node.val directly, and it returns a value, not a node.
while node: A tree node is a normal object and is truthy, and a missing child is None, which is falsy. The loop stops when the walk falls off the tree.
Rebinding, not mutating. node = node.left only moves the local name node. The tree isn't changed and root still refers to the top.
Chained conditions. p < node.val and q < node.val can't be shortened to p and q < node.val, which tests whether p is non-zero instead of comparing it. Python does allow max(p, q) < node.val, which means the same as the two comparisons.
The final else needs no condition. By then neither "both smaller" nor "both larger" holds, and that is exactly the "split or equal" case.

Complexity

Time: O(h). Every pass moves one level down or returns, and a root-to-leaf path has at most h nodes. For a balanced tree with n nodes that is O(log n). For a tree that is a single chain, such as values inserted in increasing order, it is O(n).

Space: O(1). The loop uses one variable, node. A recursive version of the same idea would use O(h) stack space.

Edge cases and common mistakes

One value is an ancestor of the other. For p = 2 and q = 4 the walk reaches 2, where 4 is larger and 2 is not smaller than itself, so neither move applies and 2 is returned. This is why the comparisons are strict.
Equal values. With p = q = 3 the walk goes down to the node holding 3 and returns 3, since a node is its own ancestor.
A single node. A tree holding only 1 with p = q = 1 returns 1.
Using <= and >=. The walk would move away from a node that equals p or q and could skip past the right answer.
Treating the tree as a general binary tree. Searching both subtrees works but costs O(n). This code relies on the BST ordering and is wrong if the tree isn't ordered.
Swapped inputs. The order of p and q doesn't matter, because both conditions treat them the same. p = 8, q = 2 also gives 6.

Testing

On the tree [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]:

p = 2, q = 8 gives 6.
p = 2, q = 4 gives 2.
p = 5, q = 3 gives 4.
p = 3, q = 3 gives 3.
p = 7, q = 9 gives 8.
p = 0, q = 5 gives 2.

Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free