#0240

Lowest Common Ancestor in a BST

MediumDSA28 min20 XP

Problem

A BST node is [value, left, right]. Given two target values p and q that exist in the tree, return the value of their lowest common ancestor.

Why This Matters

LCA in a BST shows how ordering lets you discard entire subtrees without traversing everything.

Function Signature

def lca_bst(root, p, q):

Examples

Example 1

Inputroot = [6, [2, [0, None, None], [4, None, None]], [8, [7, None, None], [9, None, None]]], p = 2, q = 8

Output6

2 is on the left of 6 and 8 is on the right, so 6 is where the paths split.

Constraints

Return the exact requested value.
Handle empty or small inputs when the prompt allows them.
Prefer the target DSA pattern over brute force when the input can grow.

CodePython

def lca_bst(root, p, q):
    """
    Input example: root = [6, [2, [0, None, None], [4, None, None]], [8, [7, None, None], [9, None, None]]], p = 2, q = 8
    Return: 6
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return None

def lca_bst(root, p, q):
    """
    Input example: root = [6, [2, [0, None, None], [4, None, None]], [8, [7, None, None], [9, None, None]]], p = 2, q = 8
    Return: 6
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return None

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Different sides

Inputp = 2, q = 8

Expected6

The targets split at the root.

Ancestor is one target

Inputp = 2, q = 4

Expected2

A node can be the ancestor of itself.

Hidden Test Categories

both targets in left subtreeboth targets in right subtreetargets passed in reverse order