Lowest Common Ancestor of a Binary Tree

Given a binary tree and two distinct node values p and q, your task is to find the lowest common ancestor (LCA) of the two nodes. The lowest common ancestor is defined as the deepest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

You are provided with the tree in level-order format where each node value is separated by a space and the placeholder 'null' represents a missing node. It is guaranteed that all node values in the tree are unique.

inputFormat

The input consists of three lines:

1. The first line contains the level-order traversal of the binary tree with each node separated by a space. Use the string 'null' for missing nodes.
2. The second line contains an integer representing the value of node p.
3. The third line contains an integer representing the value of node q. It is guaranteed that both p and q exist in the tree.

outputFormat

Output a single integer representing the value of the lowest common ancestor of the two given nodes.## sample

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

5