#9MediumTrees· Ancestor Queries

Lowest Common Ancestor of a Binary Tree

You are given the `root` of a binary tree (not necessarily a search tree) whose node values are all distinct, and two values `p` and `q` that both occur in the tree. Return the value of their **lowest common ancestor**: the deepest node that has both `p` and `q` in its subtree. A node counts as being in its own subtree, so if `p` is an ancestor of `q`, the answer is `p`. The tree is given as a level-order array: values are listed breadth-first, left to right, and `null` marks a missing child. Children of a missing node are not listed.

Input format

root: level-order array with `null` for missing children, p: integer, q: integer

Output format

Integer: the value of the lowest common ancestor

Examples

Input: root = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9], p = 8, q = 9

Output: 5

8 and 9 are the two children of node 5.

Input: root = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9], p = 8, q = 7

Output: 1

8 is in the left subtree of the root and 7 is in the right subtree, so they only meet at the root.

Input: root = [1, 2, 3, 4, 5, 6, 7, null, null, 8, 9], p = 5, q = 9

Output: 5

5 is an ancestor of 9, and a node counts as its own ancestor.

Constraints

2 <= number of nodes <= 10^4
-10^9 <= Node.val <= 10^9
All node values are distinct.
p != q, and both p and q exist in the tree.

Study first

Trees & Binary Search Trees

#trees
#binary-tree
#breadth-first-search
#hash-table