## 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;
}``````

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

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

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

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);
}``````

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..

Comment hidden because of low score. Click to expand.
0

my bad, above solution is correct

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

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.

### 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.

### 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.

### 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.