Binary Tree Level Order Traversal or Breadth First Traversal

A tree having at most 2 children called Binary Tree.

Fig 1 Binary Tree

Every tree has a root node. In Fig 1, node with value 1 is root node.

Level Order Traversal

In level order traversal we traverse node level by level. In level 0 we have one node with value 1.

Level 1=> 2 nodes with value 2,3

Level 2=> 4 nodes with value 4,5,6,7

Level 3=> 6 nodes with value 8,9,10,11,12,13,14

Level order traversal for above tree is.

1,2,3,4,5,6,7,8,9,10,11,12,13,14

Algorithm for traversal is as follows:

1. Take a queue named q
2. If root!==null, push root in q
3. Remove first value from q and call it node
4. print node value
5. push left child and right child of node into queue if they are not null
6. repeat 3,4,5 till q is not empty.

Code is as below.

levelOrder(root) {
let q = [];
if (root !== null) q.push(root);
while (q.length !== 0) {
const node = q.shift();
console.log(node.data);
if (node.left != null) q.push(node.left);
if (node.right != null) q.push(node.right);
}
}

levelorder is a method which takes root of tree as a parameter.