102. Binary Tree Level Order Traversal

MediumTreeBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

The given problem is about performing a level order traversal on a binary tree. In a level order traversal, we visit all the nodes of a tree level by level, starting from the root. We start at the root level, then move to the nodes on the next level, and continue this process until all levels are covered. The goal is to return the values of the nodes in an array of arrays, where each inner array represents a level in the tree and contains the values of the nodes at that level, ordered from left to right.

Intuition

To solve this problem, we use an algorithm known as Breadth-First Search (BFS). BFS is a traversal technique that explores the neighbor nodes before moving to the next level. This characteristic of BFS makes it perfectly suited for level order traversal.

To implement BFS, we use a queue data structure. The queue helps us process nodes in the order they were added, ensuring that we visit nodes level by level. Here's the step-by-step intuition behind the solution:

  1. If the root is None, the binary tree is empty, and we have nothing to traverse. Therefore, we return an empty list.

  2. Initialize an empty list ans to store the level order traversal result, and a queue q (implemented as a deque to allow for efficient pop and append operations) with the root node as the starting point.

  3. We want to process each level of the tree one at a time. We do this by iterating while there are still nodes in our queue q.

  4. For each level, we initialize a temporary list t to store the values of the nodes at this level.

  5. Before we start processing the nodes in the current level, we note how many nodes there are in this level which is the current size of our queue q.

  6. We then dequeue each node in this level from q, one by one, and add their values to our temporary list t. For each node we process, we check if they have a left or right child. If they do, we enqueue those children to q. This prepares our queue for the next level.

  7. Once a level is processed, we append our temporary list t to ans.

  8. Continue the process until there are no more nodes left in the queue, meaning we have visited all levels.

  9. Return ans, which contains the level order traversal result. Each inner list within ans represents node values at a respective level of the tree.

The breadth-first nature of the queue ensures that we visit all nodes at a given depth before moving on to nodes at the next depth, fitting the needs of a level order traversal perfectly.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Solution Approach

The implementation of the solution primarily involves utilizing the Breadth-First Search (BFS) algorithm with the help of a queue data structure to traverse the tree. The code involves the following steps:

  1. Initialization: We first define a class Solution with the method levelOrder, which takes the root of the binary tree as an input. We initialize an empty list ans to hold our results. If the root is None, we immediately return the empty list as there are no nodes to traverse.

  2. Queue Setup: We initialize a queue q (typically implemented as a double-ended queue deque in Python for efficient addition and removal of elements). We add the root to the queue to serve as our starting point for the level order traversal.

  3. Traversal Loop: We then enter a while loop, which will run until the queue is empty. This loop is responsible for processing all levels in the tree.

  4. Level Processing: Inside the loop, we start by creating a temporary list t to store node values for the current level. Since queue q currently holds all nodes at the current level, we use a for loop to process the number of nodes equal to the current size of the queue. For each node:

    • We dequeue the node from q using popleft.
    • We add the node's value to the temporary list t.
    • If the node has a left child, we add it to the queue.
    • Similarly, if the node has a right child, we add it to the queue as well.

    After we process all nodes at the current level, their children are in the queue, ready to be processed for the next level.

  5. Appending to Result: Once we finish processing all nodes at one level, we append temporary list t, which contains the values of these nodes, to our main result list ans.

  6. Completion: After the while loop exits (the queue is now empty since all nodes have been visited), we return ans. The list ans now holds the node values for each level of the binary tree, arranged from top to bottom and left to right, as required by the problem.

The BFS approach ensures we process all nodes at one level before moving onto the next, aligning with the level order traversal definition. By taking advantage of the queue to keep track of nodes to visit and maintaining a list for each level's node values, the solution effectively combines data structure utilization with traversal strategy to solve the problem efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's illustrate the solution approach with a small binary tree example.

Consider the following binary tree:

1    1
2   / \
3  2   3
4 /   / \
54   5   6

Here's how the level order traversal would process this tree:

  1. Initialization: We create an instance of Solution and call the method levelOrder with the root of the tree (node with value 1). We also initialize an empty list ans to store the result of the traversal.

  2. Queue Setup: We initialize a queue q and add the root node with value 1 to it.

  3. Traversal Loop: The queue is not empty (it contains the root), so we start the while loop.

  4. Level Processing - First Iteration

    • Create a temporary list t to store node values for this level.
    • The current queue size is 1, so the loop runs for one iteration.
    • We dequeue the root node (value 1) from the queue and add it to list t (which is now [1]).
    • The root node has two children, nodes with values 2 and 3, which we add to the queue.

  5. Appending to Result: We've finished processing the first level and append t to ans (which is now [[1]]).

  6. Level Processing - Second Iteration

    • Since the queue has two elements (values 2 and 3), we process two nodes this round.
    • Dequeue node with value 2, add it to temporary list t, and enqueue its child (value 4 to queue).
    • Dequeue node with value 3, add it to t, and enqueue its children (values 5 and 6 to queue).
    • At the end of this iteration, t has [2, 3], and the queue has nodes 4, 5, and 6.

  7. Appending to Result: We've finished processing the second level and append t to ans (which is now [[1], [2, 3]]).

  8. Level Processing - Third Iteration

    • This time queue size is 3, and we process nodes 4, 5, and 6 similarly.
    • We end up with t having [4, 5, 6], and the queue is now empty.

  9. Appending to Result: The third level is processed, and we append t to ans (which is now [[1], [2, 3], [4, 5, 6]]).

  10. Completion: The queue is empty, so the loop ends and we return ans. The final result is [[1], [2, 3], [4, 5, 6]], which correctly represents the level order traversal of the tree.

The traversal has visited all nodes level by level and has constructed a list of node values for each level, fitting the problem requirements perfectly.

Solution Implementation

1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10class Solution:
11    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
12        # Initialize a list to hold the level order traversal result
13        result = []
14      
15        # If the tree is empty, return the empty list
16        if root is None:
17            return result
18      
19        # Use a queue to keep track of nodes to visit, starting with the root node
20        queue = deque([root])
21      
22        # Loop until the queue is empty
23        while queue:
24            # Temporary list to store the values of nodes at the current level
25            level_values = []
26          
27            # Iterate over nodes at the current level
28            for _ in range(len(queue)):
29                # Pop the node from the left side of the queue
30                current_node = queue.popleft()
31                # Append the node's value to the temporary list
32                level_values.append(current_node.val)
33              
34                # If the node has a left child, add it to the queue for the next level
35                if current_node.left:
36                    queue.append(current_node.left)
37                # If the node has a right child, add it to the queue for the next level
38                if current_node.right:
39                    queue.append(current_node.right)
40          
41            # Append the list of values for this level to the result list
42            result.append(level_values)
43      
44        # Return the result list containing the level order traversal
45        return result
46
1import java.util.List;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.ArrayDeque;
5
6// Definition for a binary tree node.
7class TreeNode {
8    int val;
9    TreeNode left;
10    TreeNode right;
11    TreeNode() {}
12    TreeNode(int val) { this.val = val; }
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    // Method to perform a level order traversal of a binary tree.
22    public List<List<Integer>> levelOrder(TreeNode root) {
23        // Create a list to hold the result.
24        List<List<Integer>> result = new ArrayList<>();
25      
26        // Return an empty list if the tree is empty.
27        if (root == null) {
28            return result;
29        }
30      
31        // Create a queue to hold nodes at each level.
32        Deque<TreeNode> queue = new ArrayDeque<>();
33      
34        // Start the level order traversal from the root.
35        queue.offer(root);
36      
37        // While there are nodes to process
38        while (!queue.isEmpty()) {
39            // Temporary list to store the values of nodes at the current level.
40            List<Integer> level = new ArrayList<>();
41          
42            // Process all nodes at the current level.
43            int levelLength = queue.size();
44            for (int i = 0; i < levelLength; ++i) {
45                // Retrieve and remove the head of the queue.
46                TreeNode currentNode = queue.poll();
47              
48                // Add the node's value to the temporary list.
49                level.add(currentNode.val);
50              
51                // If the left child exists, add it to the queue for the next level.
52                if (currentNode.left != null) {
53                    queue.offer(currentNode.left);
54                }
55              
56                // If the right child exists, add it to the queue for the next level.
57                if (currentNode.right != null) {
58                    queue.offer(currentNode.right);
59                }
60            }
61          
62            // Add the temporary list to the result list.
63            result.add(level);
64        }
65      
66        // Return the list of levels.
67        return result;
68    }
69}
70
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    /**
16     * Performs a level order traversal of a binary tree and returns the values of nodes at each level
17     * as a 2D vector.
18     *
19     * @param root The root node of the binary tree.
20     * @return A 2D vector where each inner vector contains the values of nodes at the corresponding level.
21     */
22    vector<vector<int>> levelOrder(TreeNode* root) {
23        vector<vector<int>> levels;  // Stores the values of nodes at each level
24        if (!root) return levels;   // If the tree is empty, return an empty vector
25
26        // Initialize a queue to assist in BFS traversal
27        queue<TreeNode*> nodesQueue;
28        nodesQueue.push(root);
29
30        while (!nodesQueue.empty()) {
31            int levelSize = nodesQueue.size(); // Number of nodes at the current level
32            vector<int> currentLevel;          // Vector to store values of node at current level
33          
34            while (levelSize > 0) {
35                TreeNode* currentNode = nodesQueue.front(); // Take the front node in the queue
36                nodesQueue.pop();                           // Remove that node from the queue
37
38                // Add current node's value to current level vector
39                currentLevel.push_back(currentNode->val);
40
41                // If the current node has a left child, add it to the queue
42                if (currentNode->left) {
43                    nodesQueue.push(currentNode->left);
44                }
45                // If the current node has a right child, add it to the queue
46                if (currentNode->right) {
47                    nodesQueue.push(currentNode->right);
48                }
49
50                levelSize--; // Decrement the counter for nodes remaining at current level
51            }
52
53            // After processing all nodes at the current level, add the current level vector to the results
54            levels.push_back(currentLevel);
55        }
56
57        return levels; // Return the 2D vector with all the levels' values
58    }
59};
60
1// Function to perform level order traversal on a binary tree and return the values in level-wise order.
2function levelOrder(root: TreeNode | null): number[][] {
3    // Initialize the result array.
4    const result: number[][] = [];
5
6    // If the root is null, the tree is empty, and we return the empty result.
7    if (root === null) {
8        return result;
9    }
10
11    // Initialize a queue to hold nodes at each level.
12    const queue: TreeNode[] = [root];
13
14    // Iterate until the queue is empty.
15    while (queue.length !== 0) {
16        // Get the number of nodes at the current level.
17        const levelLength = queue.length;
18
19        // Process all nodes at the current level.
20        const currentLevelValues: number[] = [];
21        for (let i = 0; i < levelLength; i++) {
22            // Shift the first node from the queue.
23            const currentNode = queue.shift();
24
25            // Proceed if the currentNode is not null.
26            if (currentNode) {
27                // Add the value to the current level's result.
28                currentLevelValues.push(currentNode.val);
29
30                // Add left and right children if they exist.
31                if (currentNode.left) queue.push(currentNode.left);
32                if (currentNode.right) queue.push(currentNode.right);
33            }
34        }
35
36        // Add the current level's values to the overall result array.
37        result.push(currentLevelValues);
38    }
39
40    // Return the result array containing the level order traversal.
41    return result;
42}
43
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

The given Python code implements a level order traversal of a binary tree, where root is the root of the binary tree.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the total number of nodes in the binary tree. This is because each node in the tree is visited exactly once during the traversal.

Space Complexity:

The space complexity of the algorithm can be analyzed in terms of two components: the space used by the data structure q (which holds the nodes at the current level), and the space for the ans list.

The worst-case space complexity is O(w), where w is the maximum width of the tree. This worst case occurs when the binary tree is a complete binary tree or has the most nodes at one level. Space is needed to store all nodes of the widest level in the data structure q at one time.

Therefore, the overall space complexity of the algorithm is O(w) if we only consider the space taken by the queue. If we add the space taken by the output list ans, the total space complexity remains O(n) since ans will eventually contain all nodes of the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ