General

No Comments

Level Order Traversal of a Binary Tree

Level Order Traversal, also known as Breadth-First Search (BFS) for trees, is a method of traversing a binary tree level by level. This means we visit every node on a level before moving to the next level. It is a fundamental tree traversal algorithm that is widely used in various applications such as serialization/deserialization of trees, solving puzzles, and more.

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example

Input:

    3
   / \
  9  20
    /  \
   15   7

Output:

[[3], [9, 20], [15, 7]]

Approach: Using a Queue

To achieve Level Order Traversal, we use a queue. The idea is to use the queue to keep track of nodes at the current level, and as we process each node, we add its children to the queue for processing the next level.

Steps

  1. Initialize an empty queue and push the root node to it.
  2. While the queue is not empty, do the following:
    • Initialize an empty array to hold the values of the nodes at the current level.
    • Get the number of nodes at the current level (size of the queue).
    • For each node at the current level, dequeue the node, add its value to the current level array, and enqueue its left and right children (if they exist).
    • Add the current level array to the result array.
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const levelOrderTraversal = (root) => {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const currentNode = queue.shift();
      currentLevel.push(currentNode.val);

      if (currentNode.left) {
        queue.push(currentNode.left);
      }

      if (currentNode.right) {
        queue.push(currentNode.right);
      }
    }

    result.push(currentLevel);
  }

  return result;
};

// Test the function
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(levelOrderTraversal(root)); // Output: [[3], [9, 20], [15, 7]]

Explanation

  1. TreeNode Class: A simple class to create tree nodes, with properties for value (val), left child (left), and the right child (right).
  2. levelOrderTraversal Function:
    • If the root is null, return an empty array.
    • Initialize an empty array result to store the final traversal.
    • Initialize a queue with the root node.
    • While the queue is not empty:
      • Determine the number of nodes at the current level (levelSize).
      • Initialize an empty array currentLevel to hold the values of nodes at the current level.
      • For each node at the current level:
        • Dequeue the node, add its value to currentLevel.
        • Enqueue the left and right children of the node (if they exist).
      • Add currentLevel to result.
    • Return result.

Close Menu