Given a binary tree with the usual left and right pointers on each node, and additionally a parent pointer, make an algorithm to discover the closest ancestor to 2 nodes on the tree.

Question

analog76 · Accepted Answer

thanks @naipton.
1) Find matching node for the first value in the tree. If the node found create a set contains all its parents till the root.
2) Use postorder traversal for recording all the ancestor.
3) P1 is parent, P2 is grand parent and P3 is ggparent and continue till root.
   V1={P1,P2,P3,P4,....root}

4) Similary find all the parent of second value
    V2={P1,P2,P3,.root}.
5) traverse both set and first matching element in both sets  is lowest common ancestor.

kvr · Answer

Find height of node 1 as h1 and height of node 2 as h2 by travelling to the root.  Time O(2 lg N).  If h1 > h2, then move node1 by h1 - h2 and vice versa.  THen, use two pointers to move one parent at a time until parent nodes are same.

Complexity - O( 3 lg N)

baconmania · Answer

Assuming each node has a unique ID (its memory address, for example), you can solve this in O( 2 lg N ) where N is the number of nodes in the tree.

findCommonAncestor(Node x, Node y):
1. Initialize a hashmap, call it `parentsMap`.
2. Starting from x, visit all its parents up to and including the tree root, and for each parent `p`, set parentsMap[p.id] = true
3. Starting from y, begin to visit its parents and for each parent `p`, check parentsMap[p.id]. If true, return p.id. Else, continue visiting parents until `p` is null, at which point we return null.

analog76 · Answer

Time complexity is : O(max height of binary tree)

public void findCommonAncestor(Node current,int a,int b){
		 
		 if(current.getKey() a && current.getKey()>b){
			 findCommonAncestor(current.getLeft(), a, b);
		 }else{
			 System.out.println(" least common ancestor is "+current.getKey());
		 }
	 }

clusterfudge · Answer

analog76, your solution is not complete.

analog76 · Answer

@clusterfudge, 
what do you mean by incomplete? Can you be more precise?.

Common ancestor - first encounter of node value between a and b. Otherwise either you go left or right node.

naipton · Answer

As far as I concern it is a binary tree not binary SEARCH tree.

Amazon

Question d’entretien chez Amazon

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois