Lowest Common Ancestor in a Binary Tree

You are given a binary tree and two integer values p and q. Your task is to find the Lowest Common Ancestor (LCA) of the two nodes that have the given values.

The Lowest Common Ancestor between two nodes p and q in a binary tree is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Formally, if we denote the LCA as l, then for any node n in the tree, if both p and q are in the subtree rooted at n, then l is one such node, and among all such nodes, it is the deepest in the tree.

If either p or q is not present in the tree, return None.

For the purpose of this problem, the binary tree is provided in level order where missing children are denoted by the string null (case-sensitive). All node values are unique integers.

The following binary tree is an example:

[ 3 / \ 5 1 / \ /
6 2 0 8 /
7 4 ]

For example, if p = 5 and q = 1, the LCA is 3. If p = 6 and q = 7, the LCA is 5.

inputFormat

The input consists of two lines:

• The first line contains the level order traversal of the binary tree. The node values are separated by spaces. Use the string null to denote missing nodes.
• The second line contains two integers p and q separated by a space.

You can assume that the number of nodes is at most 10⁴ and all node values are unique.

outputFormat

Output a single line containing the value of the lowest common ancestor. If either p or q is not found in the tree, output None.

## sample

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

3