Lowest Common Ancestor in a Binary Tree

Given a binary tree and two integer values corresponding to two nodes, find their lowest common ancestor (LCA). The binary tree is provided in level order traversal, where the string null represents a missing node. The LCA of two nodes p and q is defined as the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Note: All node values in the tree are unique. Your solution should use a recursive approach with an expected time complexity of \(O(n)\), where \(n\) is the number of nodes in the tree.

Implement the algorithm to compute the LCA and output the value of the lowest common ancestor of the two given nodes.

inputFormat

The input consists of two lines read from stdin:

1. The first line contains the level order traversal of the binary tree, with node values separated by spaces. Use the literal string null to indicate a missing node.
2. The second line contains two integers p and q separated by a space, representing the values of the nodes for which you need to determine the lowest common ancestor.

outputFormat

Output a single integer to stdout representing the value of the lowest common ancestor (LCA) of the nodes with values p and q.

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

3