Coders Crushby Napplied AI
Back to DSA Problems
MediumLeetCode #235Trees

Lowest Common Ancestor of BST

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Constraints
The number of nodes in the tree is in the range [2, 10^5], All Node.val are unique
Coders Crushby Napplied AI

The ultimate interview preparation platform. Master System Design, DSA, and tackle community challenges to crush your FAANG interviews.

System Design

  • All Problems
  • Easy
  • Hard

DSA

  • All Problems
  • Dynamic Programming
  • Graphs

More

  • Problems Arena
  • Growth Paths
  • AI Discovery

Coders Crush by Napplied AI - Built for engineers preparing for FAANG/MAANG interviews

Examples
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Solution

Approach

Use BST property: if both p and q are smaller, go left; if both are larger, go right; otherwise current node is LCA.

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    return None
Complexity
Time:O(h)
Space:O(1)
Hints
  • 1.Use BST property
  • 2.If both nodes are on same side, continue that direction
  • 3.Split point is the LCA
Asked at
GoogleAmazonMetaMicrosoftLinkedIn