Lowest Common Ancestor in a Binary Tree

Find the deepest node that is an ancestor of two given nodes in a binary tree.

binary-tree dfs recursion lca tree-traversal

Given a binary tree where each node has a unique integer value and two node values `v1` and `v2` that are guaranteed to exist in the tree, write a function `lowest_common_ancestor(root, v1, v2)` that returns the value of the lowest common ancestor (LCA) of the nodes with values `v1` and `v2`.

The LCA is defined as the deepest node that is an ancestor of both nodes. A node is considered an ancestor of itself, so if one value is an ancestor of the other, that ancestor is the LCA.

You are given a `TreeNode` class as defined below. Implement the function in Python. Do not mutate the tree. The tree is represented using the provided `TreeNode` class with `.val`, `.left`, `.right` attributes. If the tree contains only one node, that node is the LCA of any two values that both equal that node's value (though in practice `v1` and `v2` will both be the same value in that case).

Constraints

- The number of nodes in the tree is between 1 and 10^5.
- Node values are unique integers within the range [-10^9, 10^9].
- `v1` and `v2` are guaranteed to exist in the tree.
- It is not guaranteed that `v1 != v2`.
- Expected time complexity: O(n), where n is the number of nodes.
- Expected auxiliary space complexity: O(h), where h is the height of the tree (recursion stack).

Example

>>> # Construct the following binary tree:
>>> #         3
>>> #        / \
>>> #       5   1
>>> #      / \ / \
>>> #     6  2 0  8
>>> #       / \
>>> #      7   4
>>> root = TreeNode(3)
>>> root.left = TreeNode(5)
>>> root.right = TreeNode(1)
>>> root.left.left = TreeNode(6)
>>> root.left.right = TreeNode(2)
>>> root.right.left = TreeNode(0)
>>> root.right.right = TreeNode(8)
>>> root.left.right.left = TreeNode(7)
>>> root.left.right.right = TreeNode(4)
>>> lowest_common_ancestor(root, 5, 1)
3
>>> lowest_common_ancestor(root, 5, 4)
5
>>> lowest_common_ancestor(root, 6, 8)
3

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think recursively: the LCA of two nodes in a tree is in the left subtree, right subtree, or is the root itself.

If both nodes are found in one subtree, recurse into that subtree. If they are split between subtrees, the current node is the LCA.

Handle the case where one of the target values equals the current node's value — that node is an ancestor of the other if the other is in its subtree.

You can search both subtrees and return a sentinel (like None) to indicate the node was not found.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.