Level Order Traversal

Binary Trees Theory/Traversals Easy

Fun fact: The problem of level order traversal is used extensively in real-world applications
For example, in networking, when you want to send a message to all systems in a network, you can model the network as a binary tree and use level order traversal to reach each system effectively
Additionally, in file systems, this method can help to retrieve files in a hierarchical structure
The implementation of garbage collection in Java also uses this concept of level order traversal, which is crucial in memory management in the software industry

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).

Examples:

Input : root = [3, 9, 20, null, null, 15, 7]

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

Explanation :

Input : root = [1, 4, null, 4 2]

Output : [ [1] , [4] , [4, 2] ]

Explanation :

Input : root = [5, 1, 2, 8, null, 4, 5, null, 6]

Constraints

0 <= Number of Nodes <= 2000
-1000 <= Node.val <= 2000

Hints

A queue (FIFO) is the best way to handle level order traversal since we process nodes level by level.
Push the root node into the queue. While the queue is not empty, process all nodes at the current level, then enqueue their left and right children for the next level.

Company Tags

Walmart Morgan Stanley Freshworks Texas Instruments Bloomberg Deloitte Square Chewy Zoho Electronic Arts KPMG Bungie Unity Technologies Etsy Optum Wayfair Nutanix Pinterest Western Digital MongoDB Roche Roblox Teladoc Health Mastercard Salesforce Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

Intuition

To traverse a binary tree level by level and capture the values of nodes at each level, we use a method known as level-order traversal. This approach involves examining nodes one level at a time, starting from the root and moving downward through the tree. By using a queue to keep track of nodes at each level, we ensure that nodes are processed in the order they appear at each level. This method efficiently organizes nodes into a 2D structure where each sub-array represents a level of the tree, capturing the complete structure of the tree from top to bottom.

Approach

To perform a level-order traversal iteratively, follow these steps:

Start by initializing an empty queue to hold nodes as we traverse the tree level by level.
Enqueue the root node into the queue. If the tree is empty, return an empty 2D vector immediately.
While the queue is not empty, process each level of the tree:
- Determine the number of nodes at the current level by checking the size of the queue.
- Create a temporary vector to store the values of nodes at this level.
- For each node at the current level:
  - Dequeue the front node from the queue.
  - Store the node’s value in the temporary vector.
  - Enqueue the left and right children of the current node (if they exist) into the queue.
- After processing all nodes at the current level, add the temporary vector to the final 2D vector representing the level order traversal.
Once all levels are processed, return the 2D vector containing the level-order traversal of the binary tree.

Dry Run

Here's how the level-order traversal works step-by-step:

Step 1: Initialise an empty queue and a 2D vector to store the level-order traversal result. If the binary tree is empty, return this empty 2D vector.
Step 2: Add the root node to the queue. This starts the traversal process from the top of the tree.
Step 3: While the queue is not empty, perform the following:
- Get the size of the queue, which indicates the number of nodes at the current level.
- Create a temporary vector to store the nodes' values for the current level.
- Iterate through the number of nodes at the current level:
  - Dequeue the front node from the queue.
  - Add the node’s value to the temporary vector.
  - Enqueue the left and right children of this node (if they exist) into the queue.
- After processing all nodes at the current level, add the temporary vector to the 2D vector.
Step 4: Once the traversal is complete, return the 2D vector which now contains the level-order traversal of the binary tree.

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data; 
    TreeNode* left; 
    TreeNode* right;

    // Constructor with a value parameter for TreeNode
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to perform level-order traversal of a binary tree
    vector<vector<int>> levelOrder(TreeNode* root) {
        // Create a 2D vector to store levels
        vector<vector<int>> ans; 
        if (root == nullptr) {
            // If the tree is empty, return an empty vector
            return ans; 
        }
        
        // Create a queue to store nodes for level-order traversal
        queue<TreeNode*> q; 
        // Push the root node to the queue
        q.push(root); 

        while (!q.empty()) {
            // Get the size of the current level
            int size = q.size(); 
            // Create a vector to store nodes at the current level
            vector<int> level; 

            for (int i = 0; i < size; i++) {
                // Get the front node in the queue
                TreeNode* node = q.front(); 
                // Remove the front node from the queue
                q.pop(); 
                // Store the node value in the current level vector
                level.push_back(node->data); 

                // Enqueue the child nodes if they exist
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            // Store the current level in the answer vector
            ans.push_back(level); 
        }
        // Return the level-order traversal of the tree
        return ans; 
    }
};

// Function to print the elements of a vector
void printVector(const vector<int>& vec) {
    // Iterate through the vector and print each element
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

// Main function
int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Create an instance of the Solution class
    Solution solution; 
    // Perform level-order traversal
    vector<vector<int>> result = solution.levelOrder(root); 

    cout << "Level Order Traversal of Tree: "<< endl;

    // Printing the level order traversal result
    for (const vector<int>& level : result) {
        printVector(level);
    }

    return 0;
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null; right = null; }
 * }
 **/

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { data = val; left = null; right = null; }
}

class Solution {
    // Function to perform level-order traversal of a binary tree
    public List<List<Integer>> levelOrder(TreeNode root) {
        // Create a list to store the levels
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            // If the tree is empty, return an empty list
            return ans;
        }
        
        // Create a queue to store nodes for level-order traversal
        Queue<TreeNode> q = new LinkedList<>();
        // Add the root node to the queue
        q.add(root);
        
        while (!q.isEmpty()) {
            // Get the size of the current level
            int size = q.size();
            // Create a list to store nodes at the current level
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                // Get the front node from the queue
                TreeNode node = q.poll();
                // Add the node value to the current level list
                level.add(node.data);
                
                // Enqueue the child nodes if they exist
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            // Add the current level to the answer list
            ans.add(level);
        }
        // Return the level-order traversal of the tree
        return ans;
    }
    
    // Main method to test the level-order traversal
    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        
        // Create an instance of the Solution class
        Solution solution = new Solution();
        // Perform level-order traversal
        List<List<Integer>> result = solution.levelOrder(root);
        
        // Printing the level-order traversal result
        System.out.println("Level Order Traversal of Tree:");
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}
from collections import deque

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    # Function to perform level-order traversal of a binary tree
    def levelOrder(self, root):
        # Create a list to store levels
        ans = []
        if not root:
            # If the tree is empty, return an empty list
            return ans
        
        # Create a queue to store nodes for level-order traversal
        q = deque([root])
        
        while q:
            # Create a list to store nodes at the current level
            level = []
            for _ in range(len(q)):
                # Get the front node from the queue
                node = q.popleft()
                # Add the node value to the current level list
                level.append(node.data)
                
                # Enqueue the child nodes if they exist
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            # Add the current level to the answer list
            ans.append(level)
        # Return the level-order traversal of the tree
        return ans

# Function to print the elements of a list
def printList(lst):
    # Iterate through the list and print each element
    for num in lst:
        print(num, end=' ')
    print()

# Main function to test the level-order traversal
if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    # Create an instance of the Solution class
    solution = Solution()
    # Perform level-order traversal
    result = solution.levelOrder(root)
    
    print("Level Order Traversal of Tree:")
    # Printing the level order traversal result
    for level in result:
        printList(level)
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null) {
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Function to perform level-order traversal of a binary tree
    levelOrder(root) {
        // Create an array to store levels
        const ans = [];
        if (!root) {
            // If the tree is empty, return an empty array
            return ans;
        }
        
        // Create a queue to store nodes for level-order traversal
        const q = [];
        // Add the root node to the queue
        q.push(root);
        
        while (q.length > 0) {
            // Get the size of the current level
            const size = q.length;
            // Create an array to store nodes at the current level
            const level = [];
            
            for (let i = 0; i < size; i++) {
                // Get the front node from the queue
                const node = q.shift();
                // Add the node value to the current level array
                level.push(node.data);
                
                // Enqueue the child nodes if they exist
                if (node.left !== null) {
                    q.push(node.left);
                }
                if (node.right !== null) {
                    q.push(node.right);
                }
            }
            // Add the current level to the answer array
            ans.push(level);
        }
        // Return the level-order traversal of the tree
        return ans;
    }
}

// Function to print the elements of an array
function printArray(arr) {
    // Iterate through the array and print each element
    console.log(arr.join(' '));
}

// Main function to test the level-order traversal
(function() {
    // Creating a sample binary tree
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    
    // Create an instance of the Solution class
    const solution = new Solution();
    // Perform level-order traversal
    const result = solution.levelOrder(root);
    
    console.log("Level Order Traversal of Tree:");
    // Printing the level order traversal result
    result.forEach(level => printArray(level));
})();

Complexity Analysis :

Time Complexity: O(N) where N is the number of nodes in the binary tree. Each node of the binary tree is enqueued and dequeued exactly once, hence all nodes need to be processed and visited. Processing each node takes constant time operations which contributes to the overall linear time complexity.

Space Complexity: O(N) where N is the number of nodes in the binary tree. In the worst case, the queue has to hold all the nodes of the last level of the binary tree; the last level could at most hold N/2 nodes, hence the space complexity of the queue is proportional to O(N). The resultant vector answer also stores the values of the nodes level by level and hence contains all the nodes of the tree contributing to O(N) space as well.

Code

Problem List