235. Lowest Common Ancestor of a Binary Search Tree

MediumTreeDepth-First SearchBinary Search TreeBinary 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.

Flowchart Walkthrough

Let's analyze this problem using the Flowchart to determine if Depth-First Search (DFS) is suitable for solving Leetcode 235: Lowest Common Ancestor of a Binary Search Tree. Here's a step-by-step walkthrough:

Is it a graph?

Yes: A tree is a specific type of graph.

Is it a tree?

Yes: More specifically, it is a Binary Search Tree (BST).

Is the problem related to directed acyclic graphs (DAGs)?

No: The problem focuses on finding the lowest common ancestor in a BST, not a DAG.

Is the problem related to shortest paths?

No: We are not looking for shortest paths; our goal is to locate the lowest common ancestor of two nodes in the BST.

Does the problem involve connectivity?

No: Although a tree is inherently about connectivity (nodes connected by edges), the primary goal here isn’t to explore connectivity between all nodes, but rather to specifically find a common ancestor node.

Does the problem have small constraints?

Yes: Despite this aspect not being as specific in the flowchart and assuming typical BST problems can be efficiently handled with tree traversals like DFS, given the nature of trees and their traversal techniques (in-order, pre-order, post-order).

Conclusion: According to the flowchart, and the outlined path:

We start with a tree.
We must apply DFS.

Therefore, the path concludes at applying Depth-First Search specifically suited to navigate through a tree's structure to locate the lowest common ancestor, efficiently respecting the properties inherent to a Binary Search Tree.

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:

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.
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.
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:

Start with the root of the BST as the current node.
Compare the values of the current node (root.val) with the values of p and q.
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.
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.
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.
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:

while 1:  # Start an indefinite loop that will break once LCA is found
    if root.val < min(p.val, q.val):  # Check if both nodes are in the right subtree
        root = root.right
    elif root.val > max(p.val, q.val):  # Check if both nodes are in the left subtree
        root = root.left
    else:
        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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

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:

We start with the root of the BST, which has a value of 6.
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.
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.
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.

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

Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know