Yahoo Interview Question
Software Engineer / Developerswhy 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
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
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.
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