# Level order traversal – Breadth-first

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