Write a function to do level order in a binary tree with a slight modification. We need to print each level's data in a separate line.
The key steps in writing such a level order function is to identify where each level ends.
In order to do that we follow the following steps:
- We use a dummy node to identify a level end and put a dummy node as soon as we are done reading that level.
- First we enter root in the queue. As root is the only node at its level, we enter a dummy node after it to signal end of level.
- So when we read back nodes from queue, as soon as we see a dummy node we know that this level has ended
- When we remove a node from queue, we enter all its children in the queue.
- And as soon as we encounter a dummy node(signaling end of current level), we enter another dummy node in the queue(this signals that we have encountered all nodes in previous level and entered their children in the queue, so this level ends here).
- As we need to print each level in new line, we enter a new line when we see a dummy node
void printLevel(Node* root) { queue<Node*> q; Node *dummy = NULL; if(root == NULL) return; //Enter root in the queue else { q.push(root); q.push(dummy); } //If queue is empty then we are done. while(!q.empty()) { Node* temp = q.front(); q.pop(); //If its a dummy node if(temp == NULL) { cout<<endl; q.push(dummy); } //Else enter node's children in the queue if(temp->left!=NULL) q.push(temp->left); if(temp->right!=NULL) q.push(temp->right); //Print out node's data. cout<<temp->data<<" "; } }
No comments:
Post a Comment