Description
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Examples:
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1
Output: 2Solution in Python
Approach:
- A binary search tree (BST) has the property that for any node
N, the left child has a value less thanNand the right child has a value greater thanN. This property can help us to efficiently find the lowest common ancestor. - If both nodes
pandqare smaller than the current node, the LCA must lie in the left subtree. - If both nodes
pandqare larger than the current node, the LCA must lie in the right subtree. - If one of the nodes is on one side of the current node and the other is on the opposite side (or one of the nodes is the current node), then the current node is the LCA.
Python
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# Start from the root of the tree
current = root
# Traverse the tree to find the lowest common ancestor
while current:
# If both p and q are greater than the current node, LCA is in the right subtree
if p.val > current.val and q.val > current.val:
current = current.right
# If both p and q are smaller than the current node, LCA is in the left subtree
elif p.val < current.val and q.val < current.val:
current = current.left
else:
# We have found the split point, where p and q are on different sides or one of them is the current node
return currentExplanation:
- Start at the root:
- We begin by setting
currentto therootnode of the tree.
- We begin by setting
- Binary Search Tree property:
- Since the BST property guarantees that values in the left subtree are smaller and values in the right subtree are larger than the current node, we can use this to navigate the tree efficiently:
- If both
p.valandq.valare greater thancurrent.val, it means both nodes are in the right subtree, so we move to the right child of the current node. - If both
p.valandq.valare smaller thancurrent.val, it means both nodes are in the left subtree, so we move to the left child of the current node. - If one node is smaller and the other is larger (or one node is equal to the current node), the current node is the lowest common ancestor.
- If both
- Since the BST property guarantees that values in the left subtree are smaller and values in the right subtree are larger than the current node, we can use this to navigate the tree efficiently:
- Return the result:
- When the traversal reaches the point where one node is on the left and the other is on the right (or one of the nodes is the current node), we return the current node as the lowest common ancestor.
Solution in Javascript
JavaScript
var lowestCommonAncestor = function(root, p, q) {
// Start at the root of the tree
let current = root;
// Traverse the tree to find the lowest common ancestor
while (current) {
// If both p and q are greater than current, LCA must be in the right subtree
if (p.val > current.val && q.val > current.val) {
current = current.right; // Move to the right child
}
// If both p and q are less than current, LCA must be in the left subtree
else if (p.val < current.val && q.val < current.val) {
current = current.left; // Move to the left child
} else {
// We have found the split point: current is the LCA
return current; // Return the current node as the LCA
}
}
// In case there is no LCA (theoretically shouldn't happen since p and q exist)
return null;
};Solution in Java
Java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Start at the root of the tree
TreeNode current = root;
// Traverse the tree to find the lowest common ancestor
while (current != null) {
// If both p and q are greater than current, LCA must be in the right subtree
if (p.val > current.val && q.val > current.val) {
current = current.right; // Move to the right child
}
// If both p and q are less than current, LCA must be in the left subtree
else if (p.val < current.val && q.val < current.val) {
current = current.left; // Move to the left child
} else {
// We have found the split point, current is the LCA
return current; // Return the current node as the LCA
}
}
// In case there is no LCA (theoretically shouldn't happen since p and q exist)
return null;
}
}Solution in C++
C++
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// Start at the root of the tree
TreeNode* current = root;
// Traverse the tree to find the lowest common ancestor
while (current != nullptr) {
// If both p and q are greater than current, LCA must be in the right subtree
if (p->val > current->val && q->val > current->val) {
current = current->right; // Move to the right child
}
// If both p and q are less than current, LCA must be in the left subtree
else if (p->val < current->val && q->val < current->val) {
current = current->left; // Move to the left child
} else {
// We have found the split point, current is the LCA
return current; // Return the current node as the LCA
}
}
// In case there is no LCA (theoretically shouldn't happen since p and q exist)
return nullptr;
}
};