Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

Well this problem can be solved by taking a path[] array and storing all the elements in the array while moving to a particular path and as soon as we reach a leaf node just print the path array. Here is the working code.

#include<stdio.h>
#include<stdlib.h>

struct node {
       struct node *left;
       struct node *right;
       int data;
};

struct node *newnode(int dat) {
     struct node *newone = malloc(sizeof(struct node));
     newone->data = dat;
     newone->left = NULL;
     newone->right = NULL;
     return newone;
}

struct node *insert(struct node *root, int dat) {
       if(root == NULL) {
               return newnode(dat);
       }
       if(dat <= root->data) {
            root->left = insert(root->left, dat);
       }
       else {
            root->right = insert(root->right,dat);
       }
       return root;
}

int height(struct node *root) {
    if(root == NULL) {
            return 0;
    }
    int ldepth = height(root->left);
    int rdepth = height(root->right);
    if(ldepth > rdepth) {
              return (ldepth+1);
    }
    else {
         return (rdepth +1);
    }
}

void arrayprint(int path[], int n) {
     int i;
     for(i = 0; i < n; i++) {
           printf("%d ", path[i]);
     }
     printf("\n");
}

void printpath(struct node *root, int path[], int pathlen) {
     if(root != NULL) {
             path[pathlen++] = root->data;
     }
     if(root->left == NULL && root->right == NULL) {
                   arrayprint(path, pathlen);
     }
     else {
          printpath(root->left, path, pathlen);
          printpath(root->right, path, pathlen);
     }
}

int main() {
    struct node *root = NULL;
    root = insert(root,6);
    root = insert(root,4);
    root = insert(root,2);
    root = insert(root,5);
    root = insert(root,9);
    root = insert(root,8);
    root = insert(root,10);
    int h = height(root);
    int path[h], pathlen = 0;
    printpath(root,path,pathlen);
    system("pause");
    return 0;
}

- Spock July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make level traversation, memorize path and print all leaf nodes.

- m@}{ June 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Treat the tree as a graph and then apply bfs by choosing the selected root !! It will give only those leaves which have path from the root

- as June 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will this work?
Assuming there are n children for every node

void printPath(int []path, int pathLen, tree *root)
{
if(root==NULL) return;

path[pathLen++]=root->data;
if(root->p1==NULL && root->p2==NULL & .... & root->pn==NULL)
{
for(int i=0;i<pathLen;i++)
	print("%d\t",path[i]);
printf("\n");
}

printPath(path,pathLen,root->p1);
printPath(path,pathLen,root->p2);
printPath(path,pathLen,root->p3);
...
printPath(path,pathLen,root->pn);
}

- Anonymous June 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

perform inorder traversal and print all nodes whose left and right elements are null..

- son_of_a_thread August 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

my bad, above solution is correct

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

perform an inorder tree traversal with maintaining 2 lists(pathSoFar and finalPath) to record and maintain the path. Both the lists are filled until the last node, for the last node only fill in the finalPath and print it and end the recursive call there.. the previous will have a pathSoFar minus the recently visited node.. continue for the rest of the tree..

The solution is space constrained.. needs extra space but at a speed of O(n)

- son_of_a_thread August 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cant stop appreciating the beauty of recursion... :)

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

treat the tree as a graph and run dfs . This will solve rt?

- Wish August 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why can't we do a DFS recursively and print bottom up.

- anurag October 26, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More