Find a BST's lowest common ancestor
Find the lowest node in a binary search tree that is an ancestor of two given values known to exist in the tree.
Course progress
Problem 82 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
BST root = 6; values = 2 and 8
Expected output
6
What is happening?
2 lies in the root's left subtree and 8 lies in its right subtree. Their paths first split at node 6, making it the lowest common ancestor.
Solution strategy
Build the right mental model
Move left when both values are smaller and right when both are larger. The first split point is their lowest common ancestor.
Core concepts
binary search tree · tree traversal
Complexity
Time O(h), space O(1), where h is the tree height.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for lowest-common-ancestor-bst
using System;
class Program
{
class Node
{
public int Value { get; private set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value) { Value = value; }
}
static Node LowestCommonAncestor(Node root, int first, int second)
{
Node current = root;
while (current != null)
{
if (first < current.Value && second < current.Value) current = current.Left;
else if (first > current.Value && second > current.Value) current = current.Right;
else return current;
}
return null;
}
static void Main()
{
Node root = new Node(6) {
Left = new Node(2) { Left = new Node(0), Right = new Node(4) },
Right = new Node(8) { Left = new Node(7), Right = new Node(9) }
};
Console.WriteLine(LowestCommonAncestor(root, 2, 8).Value);
}
}Knowledge check
Questions students often ask
What is the main idea behind find a bst's lowest common ancestor?
Move left when both values are smaller and right when both are larger. The first split point is their lowest common ancestor.
What is the time and space complexity of this solution?
Time O(h), space O(1), where h is the tree height.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.