Symantec Interview Question Principal Software Engineers
Country: United States
// returns the max number of nodes in any level
int levelWithMostNodes( Node *root )
{
if( !root ) // bork out...
queue<Node *> Q;
int currNumInLevel = 0;
int maxNodesAnyLevel = 0;
Q.enqueue(root);
Q.enqueue(NULL); // NULL is a sentinel denoting end of level
while ( ! Q.empty() )
{
root = Q.dequeue();
// if we pulled off sentinel, we finished a level
if ( root == NULL )
{
if ( currNumInLevel > maxNodesAnyLevel ) {
maxNodeAnyLevel = currNumInLevel;
}
if ( !Q.empty() ) Q.enqueue(NULL); //more level(s) to delimit
// reset this as new level starts with next dequeue
currNumInLevel=0;
continue;
}
// an actual node was pulled off...
currNumInLevel++;
// add children if they exist
if ( root->left ) Q.enqueue(root->left);
if ( root->right ) Q.enqueue(root->right);
}
return maxNodesAnyLevel;
}
class Node
{
public:
const vector<Node*>& get_children() {
return children;
}
Node *add_child() {
Node* new_node = new Node();
children.push_back(new_node);
return new_node;
}
private:
vector<Node*> children;
};
If it's not a binary tree, just modify this part in the obvious way:
// add children if they exist
if ( root->left ) Q.enqueue(root->left);
if ( root->right ) Q.enqueue(root->right);
Replace the code in the above comment to:
for(auto a:root->get_children()){
Q.enqueue(a);
}
Wouldn't that be level 2 in your example, with 5 nodes?
- 010010.bin August 03, 2015