Lowest Common Ancestor of a Binary Search Tree — LeetCode 235 Python Solution

The problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

This statement is abridged. Read the full problem on LeetCode.

Example

Input

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

Output

6

Explanation

The LCA of nodes 2 and 8 is 6.

Python 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':
        while 1:
            if root.val < min(p.val, q.val):
                root = root.right
            elif root.val > max(p.val, q.val):
                root = root.left
            else:
                return root

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 235. Lowest Common Ancestor of a Binary Search Tree is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems