CareerCup

for both the nodes, find path from the Root.
Get the continuous common sequence of both the path starting from the Root.
The last node of the above sequence is the Lowest common Ancestor.

1)Find Path to both nodes and store sequence in two arrays. [O(logk)]
2)Compare array values at same index.Last common value is the LCA. [O(logk) as max length possible of array is O(logk)]

Hey anonymous..

how did you solve the lowest common ancestor problem for a binary tree.

can u write the description of the problem

Count the number of possible binary trees given the n nodes contain the same data ....

is such a vague quesion

given an n nodes with the same data , find the different ways by which it can be represented ex node1 -> right child node 2 -> rightchild node3 or node1 -> leftchild node2 -> rightchild node 3

//Each node can be the root of the binary tree
int func(int n)
{
int sum=0;
int i=0;
if (n==0)||(n==1) return 1;
for(i=0;i<n;i++)
{
sum+=f(i)*f(n-1-i);
//f(i) is the possible number of left sub-tree
//f(n-1-i) is that of right sub-tree
}
return sum;

}

seige how can u find both nodes in log k time
its not bst.

the idea is, if a node knows its left subtree contains either ONE, and right subtree contains the OTHER, it must be the least common ancestor. Then we use recursion to solve it. Below is the code, assuming we use char to indicate the node, and no two nodes have the same value in the tree.

int leastCommonAncestor(Node *root, char A, char B)
{
	if(!root)
		return 0;
	if(root->value == A || root->value == B)
		return 1;
	int left = leastCommonAncestor(root->left, A, B);
	int right = leastCommonAncestor(root->right, A, B);
	if(left == 1 && right == 1)
		printf("the least common ancester is %c\n", root->value);
	return left+right;
}

the idea is, if a node knows its left subtree contains either ONE, and right subtree contains the OTHER, it must be the least common ancestor. Then we use recursion to solve it. Below is the code, assuming we use char to indicate the node, and no two nodes have the same value in the tree.

int leastCommonAncestor(Node *root, char A, char B)
{
	if(!root)
		return 0;
	if(root->value == A || root->value == B)
		return 1;
	int left = leastCommonAncestor(root->left, A, B);
	int right = leastCommonAncestor(root->right, A, B);
	if(left == 1 && right == 1)
		printf("the least common ancester is %c\n", root->value);
	return left+right;
}

the idea is, if a node knows its left subtree contains either ONE, and right subtree contains the OTHER, it must be the least common ancestor. Then we use recursion to solve it. Below is the code, assuming we use char to indicate the node, and no two nodes have the same value in the tree.

int leastCommonAncestor(Node *root, char A, char B)
{
	if(!root)
		return 0;
	if(root->value == A || root->value == B)
		return 1;
	int left = leastCommonAncestor(root->left, A, B);
	int right = leastCommonAncestor(root->right, A, B);
	if(left == 1 && right == 1)
		printf("the least common ancester is %c\n", root->value);
	return left+right;
}

@Anonymous, the Questions Poster.
Just by answering this question you got placed in MS, very nice ? to me it sounds fishy. r u still there or been fired? i guess must have been fired in these times of slowdown.
BTW, how many people have been placed in BIGGIES after visiting this site?
+1 here for our poster.

This can be done in O(log n).

1. Traverse the 1st node in the tree and put it in the hashtable.
2. Now when you are traversing the Node 'b' then lookup O(1) in the hashtable for the value (node->data) in the table.
3. If it matched then that is your ancestor.

Running time would be O(log n) + O( log n) = O(log n).

PS: I am considering that all the values in the tree are unique.

Correct me if I am wrong !!!

anyone?

To find LCA for nodes A and B:

O((logn)^2):
1. Find in A in left subtree, B in right subtree
2. If both not found, find in A in right subtree, B in left subtree
3. If both found, current node is the common LCA
4. If one found and not the other, make a recursive to call to that branch of the tree and start from 1.

O(nlogn) with O(n) space:
1. Traverse the tree until node A is found, store the path in an array a1.
2. Traverse the tree until node B is found, store the path in an array a2.
3. Compare a1 and a2, the last common element is the LCA.

But there are better, more complicated ways of doing this in constant time using RMQ.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

JustDoIt & Siege's solutions are perfectly correct !! Thanks Guys .. Though Siege's solution will be a common thought for any one who try to crack this problem , its really something strange to come up with JustDoIt's solution ..I never thought in that line ( if i would not have checked this site or solutions to this problem ).

let node1 and node2 be the two nodes. We have as an input, pointers to node1 and node2. Lets call the pointers as node1 and node2! Assume, we are not even provided with 'root' as an input. I am assuming we have parent pointers to the node, else we cannot solve it. The catch is that both node1 and node2 are at different levels in the binary tree. We need to somehow bring it on the same level. For that lets traverse from node1 to root. Lets have a count1=depth of node1. Initially count1=0,each time u traverse upwards, do count++. You can traverse upwards bcoz of parent pointer! Do the same for node2 to root. Now we have count1 and count2. if count1==count2...they are at the same level. If count1>count2, bring "pointer to node1" (count1-count2) times.
Else If count1<count2, bring "pointer to node2" (count2-count1) times. Thus, now both node1 and node2 are at the same LEVEL. Now traverse parents of node1 and node2 until, you get a common parent. That common parent is the LEAST COMMON ANCESTOR!

Node findLowestCommonAncestor(Node root, int value1, int value2)
        {
            while (root != null)
            {
                int value = root.Value;
                if (value > value1 && value > value2)
                {
                    root = root.Left;
                }
                else if (value < value1 && value < value2)
                {
                    root = root.Right();
                }
                else
                {
                    return root;
                }
            }
            return null; // only if empty tree
        }
        // Overload it to handle nodes as well
        Node findLowestCommonAncestor(Node root, Node child1, Node child2)
        {
            if (root == null || child1 == null || child2 == null)
            {
                return null;
            }
            return findLowestCommonAncestor(root, child1.Value, child2.Value);
        }

Dunno why are ppl wasting their time giving the solution for a binary tree. Question clearly states NON BINARY TREE.

Find the position of both nodes A and B, if A < B then divide B by 2 till its value is less A, then continue the same with A and repeat it again till A = B.

The code below should work for the cases:
- A and B are in the different subtrees
- A or B is LCA
- A and B the same
- there are several nodes with a given values (A and B)

void leastCommonAncestor(Node *pRoot, Node *pA, Node *pB, bool &a_found, bool &b_found, Node **ppLCA)
{
	if(!pA || !pB)
	{
		std::cout << "Error!" << std::endl;
		return;
	}
	if(*ppLCA || !pRoot) return;
	if(pRoot->Val == pA->Val) a_found = true;
	if(pRoot->Val == pB->Val) b_found = true;
	if(!(*ppLCA) && a_found && b_found) /*A and B are the same nodes*/
	{
		*ppLCA = pRoot;
		return;
	}
	
	bool a_left_found = false, a_right_found = false, b_left_found = false, b_right_found = false;
	leastCommonAncestor(pRoot->pLeft, pA, pB, &a_left_found, &b_left_found, ppLCA);
	if(!(*ppLCA))
	{
		leastCommonAncestor(pRoot->pRight, pA, pB, &a_right_found, &b_right_found, ppLCA);
	}
	if(!(*ppLCA) && /*in case of there are several given nodes in the tree*/
	(a_left_found && b_right_found) || (a_right_found && b_left_found) || /*different subtrees*/
	(a_found && (b_left_found || b_right_found)) || (b_found &&(a_left_found || a_right_found))) /*LCA is one of given nodes*/
	{
		*ppLCA = pRoot;
		return;
	}
	if(!a_found) a_found = a_left_found || a_right_found;
	if(!b_found) b_found = b_left_found || b_right_found;
}

Check out this solution, and please comment if you find any bug:-
http : // goo.gl / gGR2V

my easy to understand answer:
1. find path of both node from root
2. compare the path,until find different ith, return path[i-1]

time complexity is O(n+n+logn)=O(n)

TreeNode lca(TreeNode root, TreeNode a, TreeNode b){
List<TreeNode> pathA = new ArrayList<>();
List<TreeNode> pathB = new ArrayList<>();
dfs(root, a, pathA);
dfs(root, b, pathB);
int i = 0;
while(pathA.get(i) == pathB.get(i)) i++;
return pathA.get(i-1);
}

boolean dfs(TreeNode root, Node a, List<TreeNode> path){
if(root==null) return false;
path.add(root);
if(root.equals(a)) return true;
if(dfs(root.left, a, path)) return true;
if(dfs(root.rigth, a, path)) return true;
path.remove(path.length() - 1);
return false;
}

1. find path of both node from root
2. compare the path,until find different ith, return path[i-1]

time complexity is O(n+n+logn)=O(n)

TreeNode lca(TreeNode root, TreeNode a, TreeNode b){
List<TreeNode> pathA = new ArrayList<>();
List<TreeNode> pathB = new ArrayList<>();
dfs(root, a, pathA);
dfs(root, b, pathB);
int i = 0;
while(pathA.get(i) == pathB.get(i)) i++;
return pathA.get(i-1);
}

boolean dfs(TreeNode root, Node a, List<TreeNode> path){
if(root==null) return false;
path.add(root);
if(root.equals(a)) return true;
if(dfs(root.left, a, path)) return true;
if(dfs(root.rigth, a, path)) return true;
path.remove(path.length() - 1);
return false;
}

Get Preorder, InOrder and PostOrder of the tree.

Then follow the steps to get the LCA of the two nodes n1 and n2.

1. S1 = {List of nodes from Preorder that fall before before n1 and n2}
2. S2 = {List of nodes from Inorder that fall are between n1 and n2}
3. S3 = {List of nodes from Postorder that fall after n1 and n2}

LCA of n1 and n2 = Intersection(S1, S2, S3)