📘

Lowest Common Ancestor of a BST

Given a BST as a level-order array and two node values p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that is an ancestor of both p and q (a node can be its own ancestor).

Example:

Input:

6,2,8,0,4,7,9,null,null,3,5
2
8

Output:

Reasoning:

The given level-order array represents a Binary Search Tree (BST) where for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node.
The BST is constructed as follows:
- Root: 6
- Left subtree: 2 (root), 0 (left child), 4 (right child), 3 (left child of 4), 5 (right child of 4)
- Right subtree: 8 (root), 7 (left child), 9 (right child)
To find the LCA of nodes p = 2 and q = 8, we observe that 2 is in the left subtree of the root (6) and 8 is in the right subtree of the root (6), meaning the root (6) is the first common ancestor of both p and q and, being the root, the deepest such ancestor.
Since 6 is the root and the first common ancestor of p and q, it is their lowest common ancestor (LCA).

Constraints:

2 <= number of nodes <= 10^5
All values unique
p != q, both exist in tree

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

6,2,8,0,4,7,9,null,null,3,5
2
8

The given level-order array represents a Binary Search Tree (BST) where for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node.
The BST is constructed as follows:
- Root: 6
- Left subtree: 2 (root), 0 (left child), 4 (right child), 3 (left child of 4), 5 (right child of 4)
- Right subtree: 8 (root), 7 (left child), 9 (right child)
To find the LCA of nodes p = 2 and q = 8, we observe that 2 is in the left subtree of the root (6) and 8 is in the right subtree of the root (6), meaning the root (6) is the first common ancestor of both p and q and, being the root, the deepest such ancestor.
Since 6 is the root and the first common ancestor of p and q, it is their lowest common ancestor (LCA).

2 <= number of nodes <= 10^5
All values unique
p != q, both exist in tree

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.