LeetCode 235: Lowest Common Ancestor Of A Binary Search Tree — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Medium — Binary Search Tree | Tree | Recursion

The Problem

Find the lowest common ancestor (LCA) of two given nodes in a binary search tree, where the LCA is the deepest node that has both nodes as descendants.

Approach

Leverage the BST property to recursively navigate the tree. If both nodes are smaller than current node, go left; if both are larger, go right; otherwise the current node is the LCA.

Time: O(h) · Space: O(h)

Code

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