Lowest Common Ancestor in a BST

Lowest Common Ancestor in a BST

Find the lowest common ancestor of two nodes in a binary search tree using its ordering property.

Input format

The first line contains level-order tokens. The second line contains X and Y (both present in the tree).

Output format

Print the value of the lowest common ancestor.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

74 10 85 3 43 N 89 N 9 14 57 N N N N N 40 N 68 N N 65
68 89

74

68 22 96 8 26 78 97 N 10 24 30 73 83 N N N 18 N N 29 47 N N 79 93 N N N N 46 50 N N N N 41
24 79

68