Least Common Ancestor of Two Nodes

You are given an arbitrary binary tree with 'N' nodes, where the nodes are numbered with values in the range of integers. Given two specific nodes, 'x' and 'y', your task is to determine and print the least common ancestor (LCA) of these nodes in the tree.

The LCA is defined as the lowest node in the tree which has both 'x' and 'y' as its descendants (or the node itself being a descendant).

Input:

The input begins with an integer 'T' indicating the number of test cases.
For each test case, you will be provided with one line containing the values of the nodes of the tree in level order format (use -1 for NULL nodes).
x y (followed by the values of x and y for which LCA is to be found)

Output:

Output the LCA of the given nodes for each test case on a new line.

Example:

Input:

1
3 5 1 -1 -1 0 8
5 1

Output:

3

Explanation:

In the provided binary tree, the node 3 is the least common ancestor of 5 and 1.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10^4
• 1 <= nodeVal <= 10^9
• Time Limit: 1 sec

Note:

Ensure that one or both nodes x and y may not be present in the tree, and you must handle references accordingly when they are NULL.