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:
- The values of both
pandqare less than the value of the current node. This means the LCA must be in the left subtree. - The values of both
pandqare 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
pandqare 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.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
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 ofpandq. - If both
pandqhave values less thanroot.val, the LCA must be in the left subtree. Therefore, update the current node to beroot.leftand continue the search. - If both
pandqhave values greater thanroot.val, the LCA must be in the right subtree. Therefore, update the current node to beroot.rightand continue the search. - If the value of
pis less thanroot.valand the value ofqis greater thanroot.val, or vice versa, this implies thatpandqlie in different subtrees of the current node. Thus, the current node must be their LCA. - In a case where either
porqis equivalent toroot.val, it means that eitherporqis 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.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
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:
- We start with the root of the BST, which has a value of 6.
- We compare the values of
pandqto the current node (root), which is 6.p.valis 2 andq.valis 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
pandq. Therefore, we have found the condition from step 5:pandqlie 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
271// 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}
361/**
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};
331// 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}
35How 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).
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.
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Got a question?ย Ask the Teaching 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.