Lowest Common Ancestor

Given a binary tree root, and integers a and b, find the value of the lowest node that has a and b as descendants. A node can be a descendant of itself.

All nodes in the tree are guaranteed to be unique.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Lowest-Common-Ancestor

Examples

Example 1

Input

• root =

• a = 3
• b = 5

Output

• answer = 2

Example 2

Input

• root =

• a = 6
• b = 4

Output

• answer = 6

Solution