LC-0235 Medium LeetCode

235. Lowest Common Ancestor of a Binary Search Tree

Tree Depth-First Search Binary Search Tree Binary Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        s, b = sorted([p.val, q.val])
        while not s <= root.val <= b:
            # Keep searching since root is outside of [s, b].
            root = root.left if s <= root.val else root.right
        # s <= root.val <= b.
        return root

Solution from kamyu104/LeetCode-Solutions · MIT