Binary Tree: Level-order Traversal

Representation

We represent the node as:

Node =>
    Value
    Node Left
    Node Right

Level-order Traversal

We traverse the tree level-by-level because we want to cover the breadth. We first traverse all the nodes in a level and then traverse the next level guaranteeing a unique visit order. We visit the root node first and then visit its child nodes, then their child nodes, etc.

The traversal is complete once we have visited all the nodes in the tree.

Level-order Traversal

Example

We will do the level-order traversal on the following binary tree:

Binary Tree for Level-order Traversal

The nodes in yellow are not yet visited. The level-order traversal visits the nodes A, B, C, D, E, F, G, and H.

Level-order Traversal

Let’s take a look at each visit separately. We start at the root node, i.e., node A and access the node.