1. Understanding the Problem

You are given a Binary Search Tree (BST) and two specific nodes within that tree, p and q. Your task is to find their Lowest Common Ancestor (LCA).

What is a Lowest Common Ancestor?

The LCA of two nodes p and q is defined as the lowest (deepest) node in the tree that has both p and q as descendants. (Note: A node is allowed to be a descendant of itself).

What is the Golden Rule of a BST?

Unlike a regular binary tree, a Binary Search Tree has a strict rule for how data is organized:

• Every node in the left subtree is smaller than the root node.
• Every node in the right subtree is larger than the root node.

2. The Core Intuition: Finding the "Split Point"

If this were a regular binary tree, we would have to exhaustively search every single branch to find where p and q are located. But because this is a BST, the tree is essentially giving us a map. We just have to read the signs.

Imagine you start at the top of the tree (the root) and look down:

• If both p and q are greater than your current node, they must both be hiding somewhere down the right branch. So, you move right.
• If both p and q are less than your current node, they must both be hiding somewhere down the left branch. So, you move left.

The "Aha!" Moment: The very first moment you find a node where p and q no longer agree on which direction to go—meaning one is smaller and one is larger, or one of them actually is the current node—you have found the split point. That exact split point is guaranteed to be the Lowest Common Ancestor!

3. The Logic Step-by-Step

Because we only ever need to travel down a single path (we never have to backtrack or search both branches), we can solve this iteratively without a recursive call stack, saving us memory.

1. Start a current pointer at the root of the tree.
2. While current is not null:
   • Check if both p.val and q.val are greater than current.val.
     • If yes, the LCA must be to the right. Update current = current.right.
   • Check if both p.val and q.val are less than current.val.
     • If yes, the LCA must be to the left. Update current = current.left.
   • If neither condition is true (meaning the values split, or one equals the current node), you have found the LCA! Return current.

4. Complexity Analysis

• Time Complexity: O(H) — Where H is the height of the tree. We visit at most one node per level. In a perfectly balanced BST, this is O(log N). In the worst-case scenario (a skewed tree that looks like a linked list), it becomes O(N).
• Space Complexity: O(1) — Because we are using a simple while loop and a single pointer (current) rather than recursion, we do not use any extra memory on the call stack.

5. Code Implementations

Expand the sections below to see the optimal O(1) space iterative implementation across different languages.

# 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':
        current = root
        
        while current:
            # If both p and q are greater than parent
            if p.val > current.val and q.val > current.val:
                current = current.right
            # If both p and q are lesser than parent
            elif p.val < current.val and q.val < current.val:
                current = current.left
            # We have found the split point, i.e. the LCA node.
            else:
                return current

/**
 * 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) {
        TreeNode current = root;
        
        while (current != null) {
            // If both p and q are greater than parent
            if (p.val > current.val && q.val > current.val) {
                current = current.right;
            } 
            // If both p and q are lesser than parent
            else if (p.val < current.val && q.val < current.val) {
                current = current.left;
            } 
            // We have found the split point, i.e. the LCA node.
            else {
                return current;
            }
        }
        
        return null;
    }
}

/**
 * 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) {
        TreeNode* current = root;
        
        while (current != nullptr) {
            // If both p and q are greater than parent
            if (p->val > current->val && q->val > current->val) {
                current = current->right;
            } 
            // If both p and q are lesser than parent
            else if (p->val < current->val && q->val < current->val) {
                current = current->left;
            } 
            // We have found the split point, i.e. the LCA node.
            else {
                return current;
            }
        }
        
        return nullptr;
    }
};

6. Conclusion: You Are Ready

You have just mastered a problem that perfectly highlights why Binary Search Trees are so incredibly efficient. Whenever an interview problem specifies that the tree is a "Binary Search Tree" rather than just a "Binary Tree," your first thought should always be: "How can I use the left-is-smaller, right-is-larger rule to eliminate half the tree at every step?" By applying the iterative Split Point technique, you achieved the perfect balance of speed and memory efficiency. Keep this pattern in mind, and you will ace your tree traversal questions!