Lowest Common Ancestor (LCA) of a Binary Tree + Variants

Given the root root of a binary tree and two nodes p and q in the tree (both guaranteed to exist), return their lowest common ancestor (LCA). The LCA is defined as the deepest node that is an ancestor of both p and q (a node can be an ancestor of itself). Input Format Line 1: integer n (nodes labeled 0..n-1) Line 2: n integers left[i] is the left child of node i (-1 if none) Line 3: n integers right[i] is the right child of node i (-1 if none) Line 4: three integers root p q Output Format Output one integer: the node id of the LCA. Constraints 1 <= n <= 2 * 10^5 -1 <= left[i], right[i] < n The structure is a valid rooted tree: no cycles and each node has at most one parent. p != q, and both p and q are reachable from root. Example Input: 7 1 3 5 -1 -1 -1 -1 2 4 6 -1 -1 -1 -1 0 3 4 Output: 1 Follow-up variants If the tree is a BST, how can you leverage the BST property to optimize LCA? If nodes have parent pointers, how can you compute LCA more efficiently? If the tree is too large to fit in memory, how would you design an approach to compute LCA (consider I/O, indexing, blocking, preprocessing, or online queries)? Example Input 7 1 3 5 -1 -1 -1 -1 2 4 6 -1 -1 -1 -1 0 3 4 Output 1