#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/binary-search-trees/lca-of-bst-solution

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/binary-search-trees/lca-of-bst-solution

Repovive

LCA of BST Solution - Binary Search Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

LCA of BST Solution

Use the ordering property

In a BST, you can determine which subtree contains each node by comparing values:

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 null

If both values are smaller, both nodes are in the left subtree. If both are larger, both are in the right subtree. Otherwise, current node is the split point—the LCA.

Time: $O(h)$ . Space: $O(1)$ .

Compare this to the general binary tree LCA which is $O(n)$ . The BST property lets us find LCA in $O(h)$ without checking both subtrees.