Lowest Common Ancestor in a Binary Tree

Given a binary tree represented as a list of nodes, each node is described by a triple \( (a, l, r) \) where \( a \) is the value of the node, and \( l \) and \( r \) are the values of its left and right children respectively. A value of -1 indicates that the child does not exist. You are also given two integers \( p \) and \( q \). Your task is to find the lowest common ancestor (LCA) of the two nodes with values \( p \) and \( q \). The LCA of two nodes \( p \) and \( q \) in a tree is defined as the lowest node that has both \( p \) and \( q \) as descendants (where we allow a node to be a descendant of itself).

Input/Output Method: Use standard input (stdin) for input and standard output (stdout) for output.

Note: It is guaranteed that the tree is valid and both nodes \( p \) and \( q \) exist in the tree.

inputFormat

The input is given via standard input and has the following format:

n
 a1 l1 r1
 a2 l2 r2
 ...
 an ln rn
 p q

Where:

• n is the number of nodes.
• Each of the next \( n \) lines contains three integers \( a \), \( l \), and \( r \), representing the value of the node and the values of its left and right children respectively. A child value of -1 indicates that the child is missing.
• The last line contains two integers \( p \) and \( q \), whose lowest common ancestor you need to find.

outputFormat

Output a single integer, the value of the lowest common ancestor of \( p \) and \( q \), on standard output.

9
3 5 1
5 6 2
1 0 8
6 -1 -1
2 7 4
0 -1 -1
8 -1 -1
7 -1 -1
4 -1 -1
5 1

3