SDE - 1

You are given an arbitrary binary tree with N nodes, whose nodes have their values in the range of integers. You are given two nodes x, y from the tree. You have to print the least common ancestor of these nodes.

Least common ancestor of two nodes x, y in a tree or directed acyclic graph is the lowest node that has both nodes x, y as its descendants.

For example look at the tree below, the LCA of node 1 and 5 is 3.

Note :

You have to return the deepest node which has both x, y as its descendants.
There may be cases where one of u or v is not present in the tree. In those cases, the reference provided to u or v will be NULL.

You are given a circular linked list having N number of nodes, where N is even. You have to split this linked list into two equal-sized circular linked lists.

Here splitting means you have to make two separate circular linked lists, one for the first N/2 nodes and one for the last N/2 nodes.

For Example :

Let the circular linked list be 1, 2, 3, 4. We have to split this into two equal-sized circular linked lists.

The problem was based on diamond variation in oops and the basics of deadlock were asked .
Then the question on tree traversal was asked at the end .