## Flipkart Interview Question

Software Engineer / Developerswon't work ... if root.left is null and root.right is not null ... then upon seeing root.left = null...it will print ..

You will print each path twice. When you reach a leaf, you will print the path twice - once for each of its null child

```
void PrintPath(node* root)
{
int array[100];
int depth=0;
PathRootToLeave(root,array,&depth);
}
void PathRootToLeave(node* root, int* pArray, int* depth)
{
if(root)
{
pArray[(*depth)++]=*((int*)root->pData);
if(root->lChild)
{
PathRootToLeave (root->lChild,pArray,depth);
(*depth)--;
}
if(root->rChild)
{
PathRootToLeave (root->rChild,pArray,depth);
(*depth)--;
}
if((!(root->lChild))&&(!(root->rChild)))
{
int i = 0;
for(i=0;i<(*depth);i++)
{
printf("[%d]", pArray[i]);
}
printf("\n");
}
}
}
```

printpaths(node root, string path)

{

if(node == NUll)

return;

if(node.left == NULL and node.right == NULL )

print path.

else

path = path + node.data;

printpaths(node.left,path);

printpaths(node.right,path);

}

Although your solution is neater, I believe it will run in O(n squared) as you are passing a string each time and it is being copied. String length is linear in size of the input. Mind you that even in a language that allows pass by reference this won't work since you do need multiple copies for this to work correctly, so pass by value and copying is your only choice.

```
void PrintPaths(Node <T> * n, std::list<Node<T> *> & items)
{
items.push_back(n);
if ( n ->lchild == NULL && n->rchild == NULL)
Print(items);
else
{
if (n ->lchild != NULL)
PrintPaths(n->lchild, items);
if (n ->rchild != NULL)
PrintPaths(n->rchild, items);
}
items.pop_back();
}
void DisplayFromRootToLeaf()
{
std::list<Node <T> *> items ;
PrintPaths(root, items);
}
```

void printpath(struct node* root, int* path, int length)

{

if (root == NULL)

{printarray(path, length);

return;

}

if (root->left == NULL and root->right==NULL)

{

printarray(path,length);

return;

}

path[length] = root->value;

printpath(root->left, path, length+1);

printpath(root->right, path, length+1);

return;

}

<pre lang="" line="1" title="CodeMonkey95734" class="run-this">import java.util.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Node root = new Node(10);

root.left = new Node(8);

root.right = new Node(13);

root.left.left = new Node(4);

root.left.right = new Node(7);

root.left.left.left = new Node(2);

root.right.left = new Node(12);

root.right.right = new Node(18);

/*

10

/ \

8 13

/ \ / \

4 7 12 18

/

2

*/

printAllPaths(root,new LinkedList<Node>());

}

public static void printAllPaths(Node nd,LinkedList<Node> list){

if(nd == null){

return;

}

list.add(nd);

if(nd.left==null && nd.right==null){

System.out.println(list);

return;

}

if(nd.left!=null){

printAllPaths(nd.left,list);

list.removeLast();

}

if(nd.right!=null){

printAllPaths(nd.right,list);

list.removeLast();

}

}

}

class Node{

int data;

Node left;

Node right;

public Node(int data){

this.data = data;

}

public String toString(){

return data+"";

}

}

</pre>

Something like this:

void BinaryTree::findPath(node* root, stack<node*> &stackPath)

{

if(root)

{

if(root->left == NULL && root->right==NULL)

{

printPath(stackPath);

}

else

{

stackPath.push(root->data);

findPath(root->left,stackPath);

findPath(root->right,stackPath);

stackPath.pop();

}

}

}

void printpath(struct node* root, int* path, int length)

{

if (root == NULL)

{printarray(path, length);

return;

}

if (root->left == NULL and root->right==NULL)

{

printarray(path,length);

return;

}

path[length] = root->value;

printpath(root->left, path, length+1);

printpath(root->right, path, length+1);

return;

}

```
public void printTree(Node root)
{
if (root == null)
{
return;
}
out1.append(root.getData());
if (root.getLeft() == null && root.getRight() == null)
{
System.out.println(out1);
}
if (root.getLeft() != null)
{
printTree(root.getLeft());
out1.setLength(out1.length() - 1);
}
if (root.getRight() != null)
{
printTree(root.getRight());
out1.setLength(out1.length() - 1);
}
}
```

PrintPaths(node root, string curPath)

- Anonymous April 08, 2011{

if(root == null)

print curPath;

PrintPaths(root.left, curPath + root.data.tostring());

PrintPaths(root.right, curPath + root.data.tostring());

}