## Amazon Interview Question

Development Support Engineerswhat if we do breadth first traversal of the tree, ending the traversal at the first leaf that we encounter?

Any comments are welcome!

void FindBottomMostLeaf(node* root, int level)

{

node* p = root;

if(!p)

{

return;

}

if(p)

{

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

{

if(!head)

{

AddLNode(level, p);

}

else

{

if(head->level <= level)

{

if(head->level < level)

{

if(head)

FreeLNode();

}

AddLNode(level, p);

}

}

}

else

{

level++;

FindBottomMostLeaf(p->left, level);

FindBottomMostLeaf(p->right, level);

}

}

}

Two ways to solve the sum:

1)Using BFS.

While doing BFS the first node that is encountered to be a leaf is the answer.

Node mod_bfs(Node root)

{

if(root==null) return null;

LinkedList<Node> l= new LinkedList<Node>();

l.add(root);

While(!l.isEmpty())

{

int size=l.size();

for(int i =0;i<size;i++)

{

Node u=l.removeFirst();

if(u.leftchild==null and u.rightchild==null) return u;

if(u.leftchild)

l.add(u.leftchild);

if(u.rightchild)

l.add(u.rightchild);

}

}

}

2)Find min depth of tree using

int Find-Depth(Node root,int level)

{

if(root==Null)return level;

level=level+1;

return min(Find-Depth(root.left,level),Find-Depth(root.right,level));

}

Then just traverse the tree using inorder or postorder or preorder and find the node that is a leaf and at level=level returned by above function.

Find the height from the root node to the leaf nodes and return the leaf node which has the min. height.

- sai October 13, 2008Please correct me if i am wrong.....