NVIDIA Interview Question
Software Engineer / Developersvoid printTree( Tree *root )
{
std::deque<Tree *> bfsQ;
Tree *node = NULL;
bfsQ.push_back( root );
while ( !bfsQ.empty() ) {
node = bfsQ.front();
node->print();
bfsQ.pop_front();
int outDegree = node->GetNumChildren();
Tree **children = new (Tree*)[outDegree];
node->getChildren( children );
for ( int i = 0; i < outDegree; ++i ) {
node = children[i];
node->print();
bfsQ.push_back( node );
}
}
}
TreeNode currNode = root;
while (true)
{
if (currNode == null)
break;
if (currNode.Left != null && currNode.Left.Visited != 1)
currNode = currNode.Left;
else if (currNode.Right != null && currNode.Right.Visited != 1)
currNode = currNode.Right;
else if (currNode.Visited == 0)
{
Console.Write(currNode.Value + " ");
currNode.Visited = 1;
}
else
currNode = currNode.Parent;
}
Breadth first traversal is one of the solution
- pacchij September 02, 2008