LeetCodee

235. Lowest Common Ancestor of a Binary Search Tree

Jump to Solution: Python Java C++ JavaScript C#

Problem 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)."

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.

Constraints:

The number of nodes in the tree is in the range [2, 10⁵]
-10⁹ <= Node.val <= 10⁹
All Node.val are unique
p != q
p and q will exist in the BST

Solution

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # If both p and q are greater than root, LCA is in right subtree
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        
        # If both p and q are smaller than root, LCA is in left subtree
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        
        # If one is smaller and one is greater, or one equals root,
        # then current root is the LCA
        return root

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, we might need to traverse from root to leaf.

Space Complexity: O(h)

Due to the recursive call stack. For a balanced BST, h = log(n).

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // If both p and q are greater than root, LCA is in right subtree
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        // If both p and q are smaller than root, LCA is in left subtree
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        
        // If one is smaller and one is greater, or one equals root,
        // then current root is the LCA
        return root;
    }
}

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, we might need to traverse from root to leaf.

Space Complexity: O(h)

Due to the recursive call stack. For a balanced BST, h = log(n).

C++ Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // If both p and q are greater than root, LCA is in right subtree
        if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        
        // If both p and q are smaller than root, LCA is in left subtree
        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        
        // If one is smaller and one is greater, or one equals root,
        // then current root is the LCA
        return root;
    }
};

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, we might need to traverse from root to leaf.

Space Complexity: O(h)

Due to the recursive call stack. For a balanced BST, h = log(n).

JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // If both p and q are greater than root, LCA is in right subtree
    if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    
    // If both p and q are smaller than root, LCA is in left subtree
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    
    // If one is smaller and one is greater, or one equals root,
    // then current root is the LCA
    return root;
};

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, we might need to traverse from root to leaf.

Space Complexity: O(h)

Due to the recursive call stack. For a balanced BST, h = log(n).

C# Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // If both p and q are greater than root, LCA is in right subtree
        if (p.val > root.val && q.val > root.val) {
            return LowestCommonAncestor(root.right, p, q);
        }
        
        // If both p and q are smaller than root, LCA is in left subtree
        if (p.val < root.val && q.val < root.val) {
            return LowestCommonAncestor(root.left, p, q);
        }
        
        // If one is smaller and one is greater, or one equals root,
        // then current root is the LCA
        return root;
    }
}

Time Complexity: O(h)

Where h is the height of the tree. In the worst case, we might need to traverse from root to leaf.

Space Complexity: O(h)

Due to the recursive call stack. For a balanced BST, h = log(n).

Approach Explanation

The solution leverages the properties of a Binary Search Tree to efficiently find the LCA:

BST Property:
- All nodes in left subtree are smaller than root
- All nodes in right subtree are greater than root
- Both subtrees are also BSTs
Algorithm Steps:
- Compare both p and q with current root
- If both are greater, go right
- If both are smaller, go left
- If split occurs or equals root, we found LCA

Example walkthrough for [6,2,8,0,4,7,9] with p=2 and q=8:

Start at root (6)
2 < 6 < 8 (split occurs)
Therefore, 6 is the LCA

Key insights:

BST property makes search efficient
No need to store parent pointers
Works for both nearby and distant nodes
Recursive solution is concise and elegant