Microsoft Interview Question: Given a tree find if any path... | Glassdoor

Interview Question

Intern Interview(Student Candidate) Bengaluru (India)

Given a tree find if any path that sums up to a given value

  the starting node may not be the root node always
Answer

Interview Answer

2 Answers

2

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

Gerardo on Dec 12, 2011
0

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)

Anurag Gupta on Dec 13, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.