Brent Robinson - 1 year ago 56
C++ Question

# Displaying null children of binary tree in output

I have a method that prints the levels of a binary tree:

``````template<class BTNode>
if (node_ptr == NULL)
{
return;
}
queue<BTNode *> q1;
queue<BTNode *> q2;

q1.push(node_ptr);

while (!q1.empty() || !q2.empty()) {
while (!q1.empty())
{
node_ptr = q1.front();
q1.pop();
cout << node_ptr->data() << " ";
if (node_ptr->left() != NULL)
{
q2.push(node_ptr->left());
}

if (node_ptr->right() != NULL)
{
q2.push(node_ptr->right());
}
}
cout << endl;
while (!q2.empty())
{
node_ptr = q2.front();
q2.pop();
cout << node_ptr->data() << " ";

if (node_ptr->left() != NULL)
{
q1.push(node_ptr->left());
}
if (node_ptr->right() != NULL)
{
q1.push(node_ptr->right());
}
}
cout << endl;
}
}
``````

I check for the children of the current node to be null and push them into the queue. How can I display "NULL" in the level output instead of just skipping it and printing nothing?

You take the pointer of the next node from the queue to print data. If this node has children (i.e. pointer to child not null), you put them in the queue. This means that in the queue you'll never have a `nullptr`.

You can solve this using a variant of the algorithm: you could put nullptr in the queue in absence of child. But you then have to make sure when you get pointers from the queue not to dereference them.

``````...
while (!q1.empty() || !q2.empty()) {
while (!q1.empty())
{
node_ptr = q1.front();
q1.pop();
if (node_ptr==nullptr) {    // if nullptr was on queue
cout << "<NULL> ";      // tell it
}
else {                      // otherwise handle data and queue its children
cout << node_ptr->data() << " ";
q2.push(node_ptr->left());    // push even if it's nullptr
q2.push(node_ptr->right());   //       "           "
}
}
... // then same for q2
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download