Level Order Traversal Pattern
What is Level Order Traversal?
Level Order Traversal is a BFS application that visits all nodes in a tree level by level, from left to right.
It's also known as Breadth-First Tree Traversal because it explores all nodes at the current level before moving to the next level.
Problem Statement
Given a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).
Example:
3
/ \
9 20
/ \
15 7
Level order traversal: [[3], [9, 20], [15, 7]]
BFS Approach
- Start with the root node and enqueue it into a queue
- While the queue is not empty:
- Get the number of nodes at the current level (queue size)
- Process all nodes at the current level and enqueue their children
- Add the current level's values to the result
- Return the result containing all levels
Implementation
Here's an implementation of the level order traversal algorithm:
Time and Space Complexity
Time Complexity:
O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity:
O(n), where n is the number of nodes in the tree. In the worst case, the queue might contain all nodes at the last level, which can be up to n/2 nodes.
Variation: Zigzag Level Order Traversal
A common variation is the zigzag level order traversal, where we traverse the tree in a zigzag pattern (left to right, then right to left, and so on).
Pattern 2: Level Order Traversal
Learn how to use BFS to traverse a tree level by level, visiting all nodes at each level before moving to the next level.
What is Level Order Traversal?
Level Order Traversal is a BFS application that visits all nodes in a tree level by level, from left to right.
It's also known as Breadth-First Tree Traversal because it explores all nodes at the current level before moving to the next level.
Example:
Tree:
3
/ \
9 20
/ \
15 7
Level order traversal: [[3], [9, 20], [15, 7]]
Explanation: We first visit the root (level 0), then all nodes at level 1 from left to right, then all nodes at level 2, and so on.
Why Use Level Order Traversal?
Level-wise Processing
Level order traversal is useful when you need to process nodes level by level, such as finding the average value of each level or finding the leftmost or rightmost node at each level.
Tree Structure Analysis
It helps in analyzing the structure of a tree, such as finding the maximum width of the tree, checking if the tree is complete, or finding the minimum depth of the tree.
Hierarchical Data
It's natural for processing hierarchical data where elements at the same level have the same importance or priority, such as organizational charts or file systems.
The BFS Approach for Level Order Traversal
1Initialize
Start with the root node and enqueue it into a queue. Initialize an empty result array to store the level order traversal.
2Process Level
Get the number of nodes at the current level (queue size) and process all these nodes, adding their values to the current level array.
3Enqueue Children
For each node at the current level, enqueue its children (left first, then right) to be processed in the next iteration.
4Repeat
Add the current level array to the result and repeat steps 2-3 until the queue is empty, meaning all levels have been processed.
Implementation
Here's an implementation of the level order traversal algorithm:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }} function levelOrderTraversal(root) { // If the tree is empty, return an empty array if (!root) { return []; } // Result array to store the level order traversal const result = []; // Queue for BFS const queue = [root]; // While there are nodes in the queue while (queue.length > 0) { // Get the number of nodes at the current level const levelSize = queue.length; const currentLevel = []; // Process all nodes at the current level for (let i = 0; i < levelSize; i++) { // Dequeue a node from the queue const node = queue.shift(); // Add the node's value to the current level currentLevel.push(node.val); // Enqueue the node's children if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } // Add the current level to the result result.push(currentLevel); } return result;} // Example usage: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); const levels = levelOrderTraversal(root);console.log(levels);// Output: [[3], [9, 20], [15, 7]]Key Insight: The key to level order traversal is processing all nodes at the current level before moving to the next level. We achieve this by getting the queue size at the beginning of each iteration, which represents the number of nodes at the current level.
Time and Space Complexity
Time Complexity
O(n), where n is the number of nodes in the tree.
Explanation: We visit each node exactly once and perform constant time operations for each node. The total time complexity is proportional to the number of nodes in the tree.
Space Complexity
O(n), where n is the number of nodes in the tree.
Explanation: In the worst case, the queue might contain all nodes at the last level, which can be up to n/2 nodes for a complete binary tree. Additionally, we need O(n) space for the result array. Overall, the space complexity is O(n).
Applications and Variations
Average of Levels
Finding the average value of nodes at each level in a binary tree, useful for analyzing hierarchical data.
Right Side View
Finding the rightmost node at each level, which would be visible if you were looking at the tree from the right side.
Minimum Depth
Finding the minimum depth of a binary tree, which is the number of nodes along the shortest path from the root node to the nearest leaf node.
Variation: Zigzag Level Order Traversal
A common variation is the zigzag level order traversal, where we traverse the tree in a zigzag pattern (left to right, then right to left, and so on).
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162function zigzagLevelOrder(root) { // If the tree is empty, return an empty array if (!root) { return []; } // Result array to store the zigzag level order traversal const result = []; // Queue for BFS const queue = [root]; // Flag to indicate the direction of traversal let leftToRight = true; // While there are nodes in the queue while (queue.length > 0) { // Get the number of nodes at the current level const levelSize = queue.length; const currentLevel = []; // Process all nodes at the current level for (let i = 0; i < levelSize; i++) { // Dequeue a node from the queue const node = queue.shift(); // Add the node's value to the current level based on the direction if (leftToRight) { currentLevel.push(node.val); } else { currentLevel.unshift(node.val); } // Enqueue the node's children if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } // Add the current level to the result result.push(currentLevel); // Flip the direction for the next level leftToRight = !leftToRight; } return result;} // Example usage: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); const levels = zigzagLevelOrder(root);console.log(levels);// Output: [[3], [20, 9], [15, 7]]How it works: We use a boolean flag to indicate the direction of traversal for each level. When traversing from left to right, we add nodes to the end of the current level array. When traversing from right to left, we add nodes to the beginning of the array (using unshift). We flip the direction after processing each level.