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 <class Record>
void AVL_tree<Record>::level_order() {
	cout << "++++++++++++++++++++++" << endl;
	if(this->root == NULL){
		cout << "EMPTY TREE" << endl;
	}else{
		cout << endl;
		queue<Binary_node<Record>*> nodeQueu;
		nodeQueu.push(this->root);
		while(!nodeQueu.empty()){
			Binary_node<Record>* entry=nodeQueu.front();
			cout<<entry->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