Finding the Lowest Common Ancestor in a Binary Search Tree | LeetCode
Introduction:
In this post, we’ll explore an efficient algorithm to find the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). We’ll discuss the problem statement, the approach to solve it, and walk through a PHP implementation.
Problem Statement:
Given a Binary Search Tree (BST) and two nodes p and q, we need to find their lowest common ancestor.
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.
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.Approach:
The key property of a BST is that for every node, its left child contains nodes with values less than the node’s value, and its right child contains nodes with values greater than the node’s value. This property enables us to efficiently navigate the tree.
We can start traversing the tree from the root node. If both p and q are greater than the current node's value, we know that their LCA lies in the right subtree. Similarly, if both p and q are less than the current node's value, we traverse to the left subtree. Otherwise, the current node is the LCA.
Code Implementation:
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param TreeNode $p
* @param TreeNode $q
* @return TreeNode
*/
function lowestCommonAncestor($root, $p, $q) {
while($root) {
if ($p->val > $root->val && $q->val > $root->val)
return $this->lowestCommonAncestor($root->right, $p, $q);
elseif ($p->val < $root->val && $q->val < $root->val)
return $this->lowestCommonAncestor($root->left, $p, $q);
else
return $root;
}
}
}Time Complexity:
The time complexity of this algorithm is O(h), where h is the height of the tree. In a balanced BST, the height is O(log n), where n is the number of nodes. However, in the worst-case scenario (a skewed tree), the height can be O(n).
Conclusion:
We’ve explored an efficient algorithm to find the lowest common ancestor in a Binary Search Tree.
