Hide sidebar
leetcode/DSA courseSystem Design

Lowest Common Ancestor of a BST

TreeBST
EasyLeetCode #235
15 min

Problem Statement

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

Example

Example 1:

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

620435879

Output: 6

Constraints

  • 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.

Solution (Recursive Approach)

The solution uses a recursive approach to find the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). The key property of a BST is that all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger.

Algorithm Steps

  • If both nodes are smaller than the current node, the LCA must be in the left subtree.
  • If both nodes are larger than the current node, the LCA must be in the right subtree.
  • If one node is smaller and the other is larger, the current node is the LCA.
620435879

Case 1: LCA is the root. Find LCA of 2 and 8.

620435879

Case 2: LCA in left subtree. Find LCA of 0 and 4.

620435879

Case 3: LCA in right subtree. Find LCA of 7 and 9.

Lowest Common Ancestor of a BST Solution

# 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: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root