Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), the task is to find the lowest common ancestor (LCA) of two given nodes in the BST. The LCA is the lowest node in the BST that has both nodes as descendants, where a node can be a descendant of itself.

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.
View editorial solution
Saving… · 9 lines
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right

class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
Console

Click Run to execute sample tests.