Find the Least common ancestor for two given nodes in a tree.
I solved this question using double recursion but the interviewer was expecting me to solve it in a better way.

Question

Find the Least common ancestor for two given nodes in a tree.
I solved this question using double recursion but the interviewer was expecting me to solve it in a better way.

Sigiloso · Accepted Answer

//i and j are the values of node, whose common ancestor is to be searched.
// too2 is the root of the tree
private static void coommonancestor(Node root2, int i, int j) 
{
	if(i == j && j == root2.data)
		System.out.println("Both nodes are same");
		
	if(root2.data  i && root2.data > j)
		coommonancestor(root2.left,i,j);
			
	if(root2.data >= i && root2.data <= j)
		System.out.println("The ancestor of "+i+" and "+j+ " is :" + root2.data);		
}

Sigiloso · Answer

//structure of a node in a Tree
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val){
      this.val = val;
}
}


//Assuming it is a binary search tree
private TreeNode getAncestor(TreeNode root, TreeNode first, TreeNode second){
         if(first==null||second==null){
                return root;
         }
         if(first.val>root.val && second.valroot.val && second.val>root.val){
               return getAncestor(root.right, first, second);
           }
           else{
                   return getAncestor(root.left, first, second)
                }
}

eBay

Pergunta de entrevista da empresa eBay

Respostas da entrevista

Empresas seguidas

Buscas de vagas