Finding the Lowest Common Ancestor in a Binary Search Tree | LeetCode

Athira Radhakrishnan
3 min readApr 5, 2024
Lowest Common Ancestor | 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.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Athira Radhakrishnan
Athira Radhakrishnan

Written by Athira Radhakrishnan

Systems Engineer | PHP | SQL | Magento | Aspiring Cybersecurity Student | Professionally active since 2021 | GitHub : https://github.com/AthiraBR

No responses yet

Write a response