CareerCup

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

Please correct me if i am wrong.....

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

int lowleaf(node *root)
{
if(root==NULL) return 1;
else
return 1+min(lowleaf(root->left),lowleaf(root->right));
}
//min returns min of 2 values

correction:
if(root==NULL) return 0;

You are returning the length,not the leaf node. :(

int *queue;
insert_into_Q(root);
int flag=0;
int i=1;
while(1)
{
int k=0;
int j=0;
while(j<i)
{
node=extract_from_Q();
if(node->left==NULL&&node->right==NULL)
{
print node->value;
flag=1;
}
insert_into_Q(node->left);
k++;
insert_into_Q(node->right);
k++;

j++;
}
if(flag)
break;
i+=k;
}

last command should be i=k;

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.