Lowest Common Ancestor (LCA) Problem

Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

Algorithm:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

Problem:
Input:
No. of nodes in the binary tree
Preorder traversal of the tree
Inorder traversal of the tree
No. of queries
Node1 Node2
.
.
.


Output:
LCA of Node1 and Node2

Code in C++:




Time complexity: O(nq) (n: no.of nodes, q: no. of queries)