Yahoo Interview Question for Software Engineer / Developers






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

Inorder traversal is only of binary trees. If there are two children it would be easy to differentiate between left and the right child. Inorder traversal is definitely not possible in case of a general tree.

- noviceprog September 14, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you define in-order for such a tree.

- Anon September 15, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why it is not possible? if every node has 3 children e.g 1st, 2nd and 3rd. and 1st<node<2nd<3rd, we could always traverse in that order.ie.
void printTree(Tree* root)
{
if(root->1st)
printTree(root->1st)
printf("%d",root->value);
if(root->2nd)
printTree(2nd)
if(root->3rd)
printTree(3rd)

}

pls comment

- Jackie September 15, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If we go by the definition of the inorder traversal, we go the left child first, then the root and then the right child of the root. If we have more than two children, say we have even number of children, then visit the first half (left) first, visit the root next and then the other half (right). I guess this satisfies the definition of the inorder traversal. If so, then inorder traversal is possible. Even in case of the odd number of children, treat the first half as the left children and the second half as the right children.

P.S. I take back my comment that it is not possible to do an inorder traversal in a tree with more than two children

- noviceprog September 19, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It will help if we can consider an array of children pointers.So that now the tree will start looking like a node in a B-tree.

- XYZ October 22, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I second him. Perhaps the question was meant to lead the discussion towards B-Trees.

- Sandeep6883@gmail.com November 23, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes i also agree. B-Trees are the most appropriate choice here!

- Ashish Agarwal December 02, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree !

- Time Pass ! March 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can do preorder traversal on any tree, You have to keep sibling pointer
preorder(node)
{
visit(node);
if(node->left)
preorder(node->left)
if(node->sibling)
preorder(node->sibling)
}

This is general tree where structure of node

node{
data
left
sibling
}

- MaYanK November 27, 2009 | Flag


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More