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

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments