Flipkart Interview Question Software Engineer / Developers
won'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());
}