Here is solutions for Lowest Common Ancestor in Binary Search Tree.

1. Understand the problem

• You are given a Binary Search Tree (BST) and two nodes p and q. You must find their Lowest Common Ancestor (LCA).

Definition:

• The LCA of two nodes p and q is the lowest (deepest) node in the tree that has both p and q as descendants

Because this is a BST, it satisfies:

left subtree < root < right subtree

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Are both p and q guaranteed to exist in the tree?

• Yes

1. Can one node be the ancestor of the other?

• Yes → then that node is the LCA

1. Is the tree guaranteed to be a valid BST (no duplicates)?

• Yes, strict BST

1. What is the max size and height of the tree?

• Up to 10^5 nodes; skewed tree possible

1. Values range? Can be negative?

• Yes, arbitrary integers

Edge cases:

- p == q

- root == p or root == q

- Completely skewed tree (like a linked list)

3. Explore examples.

• Example 1:

          6
        /   \
       2     8
      / \   / \
     0   4 7   9
        / \
       3   5

p = 2, q = 8
LCA = 6

• Example 2

p = 2, q = 4
LCA = 2 (because 2 is ancestor of 4)

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Naive (Convert to paths) - Time O(N), Space O(N)

• Idea:

  • Find path from root -> p

  • Find path from root -> q

  • Compare paths to find last common node

• Time: O(N)

• Space: O(N)

4.2. Solution 2 - Binary Tree Idea — DFS on BST (Optimal Recursive) - Time O(H), worst case O(N), best case O(logN), Space O(N)

• Key BST Insight:

  • If p and q are both smaller than root -> go left

  • If both are greater than root -> go right

  • Otherwise -> root is the LCA -> Idea chỗ này, vì nó cũng là số gần nhất với left and right.

p < root < q  → root is LCA

• Time: O(H), worst case O(N), best case O(logN) Solution 2 — DFS on BST (Optimal Recursive) Key BST Insight:

• Space: O(H) recursion stack

4.3. Iterative BST (Best for interviews) - Time O(H), Space O(1)

Same logic as Solution 2 but no recursion.

• Time: O(H)

• Space: O(1), using only a curr pointer to become root and compare curr.val with l.val and r.val.

5. Implement solutions.

5.1. Naive Solution - Time O(N), Space O(N)

def lowestCommonAncestor(self, root, p, q):
    path_p = []
    path_q = []

    self.findPath(root, p, path_p)
    self.findPath(root, q, path_q)

    # Keep track the node.
    i = 0
    while i < len(path_p) and i < len(path_q) and path_p[i] == path_q[i]:
        i += 1

    return path_p[i - 1]   # ✅ returns NODE


def findPath(self, root, target, path):
    if not root:
        return False      # ✅ boolean

    path.append(root)

    if root == target:
        return True       # ✅ boolean

    if self.findPath(root.left, target, path) or \
       self.findPath(root.right, target, path):
        return True       # ✅ boolean

    path.pop()
    return False          # ✅ boolean

• Time: O(N)

• Space: O(N)

5.2. Recursion BST - Time O(H), Space O(H).

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or not p or not q:
            return None
        if (max(p.val, q.val) < root.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif (min(p.val, q.val) > root.val):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

• Time: O(H),

• Space: O(H).

5.3. Iterative BST - Time O(H), Space O(1).

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

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        cur = root

        while cur:
            if p.val > cur.val and q.val > cur.val:
                cur = cur.right
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else:
                return cur

• Time: O(H),

• Space: O(1).

6. Dry run testcases.

          6
        /   \
       2     8
      / \   / \
     0   4 7   9
        / \
       3   5

p = 2, q = 4

Dry run:

cur = 6
2 < 6 and 4 < 6 => True
=> cur = cur.left = 2

---

cur = 2
2 > 2 ? False
4 > 2 ? True → (AND False)
2 < 2 ? False → (AND False)

=> ELSE => return 2