Loading...
You are given the root of a binary search tree whose node values are all distinct, and two values p and q that both occur in the tree.
The lowest common ancestor of two nodes is the deepest node that has both of them as descendants, where a node counts as a descendant of itself.
Return the value of the lowest common ancestor of the nodes holding p and q.
Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
Node.val ≤109Node.val are unique.p != qp and q both exist in the tree.2 is in the left subtree of 6 and 8 in the right subtree, so 6 is their lowest common ancestor.
4 is a descendant of 2, and a node is its own descendant, so the answer is 2.
Click "Run" to test with sample cases or "Submit" to run all tests.