Level-order Traversal

Lets look at the 4 options to traverse a binary tree:

• Depth First Search

  • Pre-order
  • In-order
  • Post-order

• Breadth First Search

  • Level-order

In this post, let’s explore Level-order traversal.

Visualise how it traverse

We first visit the first level, then the second and so on level by level.

1. ->              20
                 /    \
              /         \
2. ->        100         3
           /     \     /   \
3. ->    50      15  250   35
        /
4. -> 222

Answer: 20, 100, 3, 50, 15, 250, 35, 222

Code Algorithm

Here’s the code example to implmenent a Level-ordertraversal.

type BinaryNode = {
  val: string;
  left?: BinaryNode;
  right?: BinaryNode;
};

function levelOrder(root: BinaryNode): void {
  if (!root) throw new Error();
  const queue = [];
  queue.push(root);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}