## 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