235. Lowest Common Ancestor of a Binary Search Tree


Problem Description

In this problem, we are given a binary search tree (BST). Our task is to find the lowest common ancestor (LCA) of two given nodes, p and q, within this BST. The lowest common ancestor is the furthest node from the root that is an ancestor of both nodes. This means that the LCA is the node from which both p and q are descended, and it could be either of the nodes themselves if one is an ancestor of the other.

Intuition

The intuition behind the solution stems from the properties of a BST. In a BST, for any node n, all nodes in the left subtree of n have values less than n, and all nodes in the right subtree have values greater than n. When searching for the LCA of p and q, there are three possibilities:

  1. The values of both p and q are less than the value of the current node. This means the LCA must be in the left subtree.
  2. The values of both p and q are greater than the value of the current node. This means the LCA must be in the right subtree.
  3. One value is less than the current node's value and the other is greater (or one of them is equal to the current node's value). This means that the current node is the LCA because p and q are in different subtrees.

The given solution iterates over the tree without using recursion. It repeatedly compares the current node's value with p and q values to determine the direction of the search or to conclude that the current node is the LCA.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

In the provided solution, the algorithm uses iteration to navigate through the tree and find the LCA. It does so without the need for additional data structures, which keeps the space complexity at a constant O(1). There is also no recursion involved, which means the solution does not rely on the call stack and thus does not incur extra space cost due to recursion stack frames.

The algorithm can be broken down into the following steps:

  1. Start with the root of the BST as the current node.
  2. Compare the values of the current node (root.val) with the values of p and q.
  3. If both p and q have values less than root.val, the LCA must be in the left subtree. Therefore, update the current node to be root.left and continue the search.
  4. If both p and q have values greater than root.val, the LCA must be in the right subtree. Therefore, update the current node to be root.right and continue the search.
  5. If the value of p is less than root.val and the value of q is greater than root.val, or vice versa, this implies that p and q lie in different subtrees of the current node. Thus, the current node must be their LCA.
  6. In a case where either p or q is equivalent to root.val, it means that either p or q is the LCA itself, as it is an ancestor of the other node (a node to be a descendant of itself).

The algorithm continues the iteration until the condition in step 5 or 6 is met. Once either condition is met, it returns the current node, which is the LCA.

Here's a breakdown of the code:

1while 1:  # Start an indefinite loop that will break once LCA is found
2    if root.val < min(p.val, q.val):  # Check if both nodes are in the right subtree
3        root = root.right
4    elif root.val > max(p.val, q.val):  # Check if both nodes are in the left subtree
5        root = root.left
6    else:
7        return root  # Found the LCA or one of the nodes is the LCA itself

The loop will always terminate because of the BST property which ensures that, with each step, the current node is moving closer to the LCA until it is found.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider a binary search tree (BST) for our example:

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

Assume we need to find the lowest common ancestor (LCA) of nodes p with value 2 and q with value 8.

Following the solution approach:

  1. We start with the root of the BST, which has a value of 6.
  2. We compare the values of p and q to the current node (root), which is 6.
    • p.val is 2 and q.val is 8.
  3. Since 6 is greater than 2 and less than 8, it is neither solely in the left subtree nor in the right subtree relative to both p and q. Therefore, we have found the condition from step 5: p and q lie in different subtrees of the current node.
  4. According to the algorithm, we have found the LCA because one node is in the left subtree and the other node is in the right subtree of node 6.

So, the lowest common ancestor of nodes 2 and 8 in this BST is the node with the value 6. The search stops here and we return the current node (root) as the LCA.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val):
4        self.val = val
5        self.left = None
6        self.right = None
7
8
9class Solution:
10    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
11        # Loop indefinitely until the lowest common ancestor is found
12        while True:
13            # Find the smaller and larger values of p and q
14            smaller_value = min(p.val, q.val)
15            larger_value = max(p.val, q.val)
16
17            # If both p and q are on the right of the current node, move right
18            if root.val < smaller_value:
19                root = root.right
20            # If both p and q are on the left of the current node, move left
21            elif root.val > larger_value:
22                root = root.left
23            # If we are in a position where p and q are on different sides
24            # of root, or one of them is equal to root, then root is the LCA
25            else:
26                return root
27
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    // Constructor to create a new node with a given value
8    TreeNode(int value) {
9        val = value;
10    }
11}
12
13class Solution {
14
15    // Function to find the lowest common ancestor of two nodes in a binary search tree
16    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode firstNode, TreeNode secondNode) {
17        // Traverse the tree starting with the root
18        while (root != null) {
19            // If both nodes are greater than current node, search in right subtree
20            if (root.val < Math.min(firstNode.val, secondNode.val)) {
21                root = root.right; // Move to the right child
22            }
23            // If both nodes are less than current node, search in left subtree
24            else if (root.val > Math.max(firstNode.val, secondNode.val)) {
25                root = root.left; // Move to the left child
26            }
27            // We've found the lowest common ancestor node
28            else {
29                return root;
30            }
31        }
32        // In case the while loop exits without returning (it shouldn't in proper usage), return null
33        return null;
34    }
35}
36
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int value;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
8 * };
9 */
10
11class Solution {
12public:
13    // Function to find the lowest common ancestor in a binary search tree.
14    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
15        // Loop until the lowest common ancestor is found.
16        while (true) {
17            // If both p and q are greater than root, then LCA must be in the right subtree.
18            if (root->value < min(p->value, q->value)) {
19                root = root->right;
20            }
21            // If both p and q are less than root, then LCA must be on the left subtree.
22            else if (root->value > max(p->value, q->value)) {
23                root = root->left;
24            }
25            // If we are in a state where p and q are on different sides of the root,
26            // or one of them is the root itself, we've found the LCA.
27            else {
28                return root;
29            }
30        }
31    }
32};
33
1// Definition of the binary tree node class interface to illustrate the structure of nodes in the binary tree.
2interface ITreeNode {
3    val: number;
4    left: ITreeNode | null;
5    right: ITreeNode | null;
6}
7
8/**
9 * Finds the lowest common ancestor (LCA) of two nodes in a binary search tree.
10 * 
11 * @param root The root node of the binary search tree.
12 * @param nodeP The first node to find the LCA for.
13 * @param nodeQ The second node to find the LCA for.
14 * @returns The lowest common ancestor of nodeP and nodeQ.
15 */
16function lowestCommonAncestor(root: ITreeNode | null, nodeP: ITreeNode | null, nodeQ: ITreeNode | null): ITreeNode | null {
17    // Continue searching for the LCA as long as the current root is not null.
18    while (root) {
19        // If both nodes are smaller than the current root, LCA must be in the left subtree.
20        if (root.val > nodeP.val && root.val > nodeQ.val) {
21            root = root.left;
22        // If both nodes are larger than the current root, LCA must be in the right subtree.
23        } else if (root.val < nodeP.val && root.val < nodeQ.val) {
24            root = root.right;
25        // If we are in a situation where one node is on the left and the other is on the right,
26        // or one of the nodes is equal to the root, the current root is the LCA.
27        } else {
28            return root;
29        }
30    }
31  
32    // If the root is null, it means we haven't found the LCA (which should not happen in a valid BST with both nodes present).
33    return null;
34}
35

Time and Space Complexity

The time complexity of the given code is O(H), where H is the height of the binary tree. This is because the code traverses the tree from the root to the lowest common ancestor (LCA) without visiting any nodes more than once. In the worst case scenario, when the binary tree is unbalanced, the height H could be linear in respect to the number of nodes, N, resulting in a time complexity of O(N). However, in a balanced tree, time complexity is O(log N) since the height of the tree is logarithmic in respect to the number of nodes.

The space complexity of the code is O(1) regardless of the tree's structure, because it uses a fixed amount of space for pointers and without any recursive calls or additional data structures that depend on the size of the tree.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄