Lowest Common Ancestor of a BST

Medium

treebinary-search-tree

Given a BST and two values p and q that exist in it, return the value of their lowest common ancestor — the deepest node that has both among its descendants (a node may be its own descendant).

Input

Line 1: the BST in level order
Line 2: two integers p q

Output: the LCA node's value.

Example 1

Input:

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

Output:

Example 2

Input:

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

Output:

An ancestor can be the node itself.

Constraints

2 ≤ nodes ≤ 10^5
All values distinct; p ≠ q; both present.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Lowest Common Ancestor of a BST

Medium

treebinary-search-tree

Input

Line 1: the BST in level order
Line 2: two integers p q

Output: the LCA node's value.

Example 1

Input:

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

Output:

Example 2

Input:

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

Output:

An ancestor can be the node itself.

Constraints

2 ≤ nodes ≤ 10^5
All values distinct; p ≠ q; both present.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.