Lowest common ancestor in a BST
You get the root of a binary search tree and two different nodes of that tree, p and q. In a binary search tree (BST), every value in a node's left subtree (its left child and everything below it) is smaller than the node's value and every value in its right subtree is larger, so no value appears twice.
An ancestor of a node is any node on the path from the root down to it, the node itself included. The lowest common ancestor of p and q is the deepest node that is an ancestor of both. Return that node: the TreeNode object from the tree, not its value.
The examples use this tree, written in level order as [20, 10, 30, 5, 15, 25, 35, None, None, 12, 18]. In them, "node 5" means the node holding 5.
20
/ \
10 30
/ \ / \
5 15 25 35
/ \
12 18
p = node 5, q = node 18Outputnode 105 is in the left subtree of 10 and 18 is in its right subtree, so 10 is the deepest node above both.
p = node 15, q = node 12Outputnode 1512 is the left child of 15, and a node counts as its own ancestor, so the answer is 15 itself.
p = node 12, q = node 35Outputnode 2012 is on the left of the root and 35 is on the right, so the two paths split at the root.
2 ≤ number of nodes ≤ 2 × 105
-109 ≤ node value ≤ 109, all different.
pandqare different nodes, and both are in the tree.The tree is at most 500 levels deep.
The function may be called many times on the same tree.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.