Binary Tree Level Order Traversal
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).
DFS Recursive Approach 1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List> levelOrder(TreeNode root) {
List> levels = new ArrayList<>();
if(root == null) return levels;
dfs(root, 0, levels);
return levels;
}
void dfs(TreeNode node, int level, List> levels){
// If the current level is not yet in the result list, create a new level
if (level >= levels.size()) {
levels.add(new ArrayList<>());
}
// Add the current node's value to its respective level
levels.get(level).add(node.val);
// Recursively traverse left and right subtrees with increased level
if (node.left != null) {
dfs(node.left, level + 1, levels);
}
if (node.right != null) {
dfs(node.right, level + 1, levels);
}
}
}
BFS Iterative Approach 2
class Solution {
public List> levelOrder(TreeNode root) {
List> levels = new ArrayList<>();
if (root == null) return levels;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List currentLevel = new ArrayList<>();
// Process all nodes at the current level
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
// Enqueue left and right children if they exist
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// Add the current level to the result
levels.add(currentLevel);
}
return levels;
}
}
Introduction
Binary trees are a fundamental data structure in computer science, used in a variety of applications from parsing expressions to search algorithms. One of the essential operations on a binary tree is **level order traversal**, where we visit all the nodes level by level. This traversal method is often used for analyzing hierarchical data, performing breadth-first searches, and visualizing tree structures.
Definition
In level order traversal, nodes are visited level by level from the root downwards. For each level, nodes are visited from left to right. This traversal technique is particularly useful for understanding the breadth of the tree and is implemented using a queue to maintain the nodes at each level.
Consider the following binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
The level order traversal of this tree is: **1, 2, 3, 4, 5, 6, 7**.
Algorithm
Level order traversal is performed using a **Breadth-First Search (BFS)** approach. A queue is used to track nodes at the current level and enqueue their child nodes for processing at the next level.
Steps:
- Initialize an empty queue and enqueue the root node.
- While the queue is not empty:
- Dequeue the front node and process it.
- Enqueue the left child (if any) of the dequeued node.
- Enqueue the right child (if any) of the dequeued node.
Implementation
Here is the Python implementation of level order traversal:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def levelOrderTraversal(root):
if not root:
return []
queue = [root]
result = []
while queue:
current = queue.pop(0)
result.append(current.value)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return result
# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(levelOrderTraversal(root)) # Output: [1, 2, 3, 4, 5, 6, 7]
Examples
Let's analyze the traversal process for the following binary tree:
10
/ \
20 30
/ \ / \
40 50 60 70
Steps:
- Enqueue root (10). Dequeue and process 10. Enqueue 20 and 30.
- Dequeue 20. Process and enqueue 40 and 50. Dequeue 30. Process and enqueue 60 and 70.
- Dequeue and process nodes 40, 50, 60, and 70. Since they have no children, the traversal ends.
Result: 10, 20, 30, 40, 50, 60, 70
Applications
Level order traversal is widely used in various scenarios:
- **Visualizing trees**: Useful for rendering hierarchical structures like organizational charts.
- **Finding the width of the tree**: Determines the maximum number of nodes at any level.
- **Shortest path in an unweighted graph**: BFS is used to find the shortest path from a source to a destination.
- **Serialization and deserialization**: Traversal helps in converting a tree to a format suitable for storage and reconstruction.
Conclusion
Level order traversal is a fundamental technique for binary trees that provides a comprehensive understanding of the tree's structure. Whether for algorithmic problem-solving, data visualization, or applications in graph theory, mastering this technique is essential for any programmer or computer scientist.
