235. Lowest Common Ancestor of a Binary Search Tree

[#binary-tree, #dfs]

## description

## 235. Lowest Common Ancestor of a Binary Search Tree

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:

plain text

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:

plain text

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.

Example 3:

plain text

Input: root = [2,1], p = 2, q = 1
Output: 2

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

Constraints:

## notes

### Intuition

In a BST, all nodes in the left subtree are smaller and all in the right are larger. The LCA is the first node where p and q diverge—one goes left, one goes right (or one equals the current node).

### Implementation

Solve iteratively for better space. Start at the root and traverse down. If both p and q are greater than the current value, move right. If both are smaller, move left. Otherwise, we've found the split point—this is the LCA.

### Edge-cases

The problem guarantees p and q exist in the tree, so we don't need null checks for them. One node being the ancestor of another is handled naturally—the divergence point will be that ancestor.

–
Time: O(h) — traverse at most the height of the tree
–
Space: O(1) — iterative approach uses no extra space

### Complexity

## solution

python

from typing import Optional
from lcutils import TreeNode

# 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: Optional[TreeNode], p: Optional[TreeNode], q: Optional[TreeNode]) -> Optional[TreeNode]:
        curr = root
        while curr:
            if q and p and q.val > curr.val and p.val > curr.val:
                curr = curr.right
            elif q and p and q.val < curr.val and p.val < curr.val:
                curr = curr.left
            else:
                return curr



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--