Day 10 - Lowest Common Ancestor of a Binary Search Tree

🧩 Problem:

Given a binary search tree (BST) and two nodes p and q, return the lowest common ancestor (LCA) of the two nodes.

💡 Definition of LCA:
The lowest node in the tree that has both p and q as descendants (a node can 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: 6 is the split point between nodes 2 and 8.

Example 2
Input:
p = 2, q = 4
Output: 2
Explanation: A node can be an ancestor of itself.

🧠 Insight:

Because it’s a BST, we can use its properties:

• All values in the left subtree are smaller than the node.

• All values in the right subtree are greater.

So:

• If p and q are both less than current node → LCA is in the left.

• If both are greater → LCA is in the right.

• If they split directions → current node is the LCA.

✅ Python Solution:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left  # both nodes are in the left subtree
            elif p.val > root.val and q.val > root.val:
                root = root.right  # both nodes are in the right subtree
            else:
                return root  # split point — one node on each side (or equal)

⏱ Time Complexity:

• O(h), where h is the height of the tree.

• For a balanced tree, this is O(log n).

💬 TL;DR:

Binary Search Tree rules help us find the LCA without needing full recursion. If both nodes are on the same side, go deeper. If they split, you've found the answer.