Lowest Common Ancestor in a Binary Tree

You are given a binary tree represented in level order where missing nodes are denoted by "null". Your task is to find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined as the lowest node in the tree that has both nodes as descendants (a node can be a descendant of itself).

The input starts with the number of nodes in the tree (including "null" placeholders). Then follows the level order traversal of the tree. After that, two integer values are given, representing the values of nodes for which the LCA needs to be found.

Note: It is guaranteed that both given nodes exist in the tree.

The formula for the LCA (in LaTeX) can be expressed as:

$$ LCA(p, q) = \min \{ v \in T : p, q \in \text{descendants}(v) \} $$

inputFormat

The first token is an integer n, representing the number of tokens in the following level order traversal array. The next n tokens are either integers or the string "null" denoting missing children. Following the level order traversal, there are two integers, p and q, representing the values of the nodes for which you need to find the LCA.

The input is provided via standard input (stdin) with tokens separated by spaces.

outputFormat

Output a single integer which is the value of the lowest common ancestor of the two given nodes. The output should be printed to standard output (stdout).

11 3 5 1 6 2 0 8 null null 7 4 5 1

3