Here is implementation of level order traversal of a binary tree.
Level order traversal is nothing more than traversing each level at a time
10 Lev 1
/ \
9 15 Lev 2
/ / \
7 12 17 Lev 3
Output
10 9 15 7 12 17
AVL Tree example
++++++++++++++++++++++ 69: 29 77 29: 15 48 15: 5 23 5: 3 11 11: - 14 23: 16 26 16: - 18 48: 33 64 33: 32 46 64: 50 68 77: 72 84 72: 71 76 84: 80 89 80: 79 82 89: 87 93 ++++++++++++++++++++++
The level order result is: ++++++++++++++++++++++ 69 29 77 15 48 72 84 5 23 33 64 71 76 80 89 3 11 16 26 32 46 50 68 79 82 87 93 14 18 ++++++++++++++++++++++
Implementation
/**
* Implementation of Level order traversal
* Prints nodes at each level left to right
*/
template
void AVL_tree::level_order() {
cout << "++++++++++++++++++++++" << endl;
if(this->root == NULL){
cout << "EMPTY TREE" << endl;
}else{
cout << endl;
queue*> nodeQueu;
nodeQueu.push(this->root);
while(!nodeQueu.empty()){
Binary_node* entry=nodeQueu.front();
cout<data<<" ";
if(entry->left != NULL){
nodeQueu.push(entry->left);
}
if(entry->right != NULL){
nodeQueu.push(entry->right);
}
nodeQueu.pop();
}
}
cout << "\n++++++++++++++++++++++" << endl;
}
Complexity
Running time complexity of this algorithm is O(n) since every node will have to be explored