Given a tree find if any path that sums up to a given value
the starting node may not be the root node always

Question

Given a tree find if any path that sums up to a given value
the starting node may not be the root node always

Gerardo · Accepted Answer

This problem is quite difficult:

void SearchSum(Tree head, int sum, ArrayList sol, int level)
{
  if (head!=null)
  {
   sol.add(head.data);
  int aux=0;
   for(int i=sol.length;i>-1;i--)
    {
      aux+=sol[i];
     if(aux==sum)
        {
           printArray(aux,i,level);
        }
    List l1=sol.Clone();
    List l2=sol.Clone();
     SearchSum(head.left, sum, sol, level+1);
    SearchSum(head.right,  sum,sol, level+1);
    }
  }
}

void printArray(ArrayList aux,int i,int level)
{
 String sol="";
   for(int j=i;j

Anurag Gupta · Answer

well, i think this is an easy one.

we write a function which takes a node and then continues finding the desired path taking the provided node as the root oh the path(not the root of tree).

and we run this function for every node of tree.
time complexity O(n lgn)

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas