Binary Tree Level Order Traversal Problem with Examples

Binary Tree Level Order Traversal is an algorithm that processes all nodes in a tree by traversing through depth, starting with the root, then the child of the root, and so on. Let’s take a look at some of the examples to print the level order traversal line by line of the binary tree.

Binary Tree Level Order Traversal Problem Statement:

Given a binary tree, the task is to return the level order traversal of its nodes’ values, i.e., list the node values level by level from left to right.

Example One

Output:

[
[0],
[1],
[2],
[4],
[3]
]

Example Two

Output:

[
[2],
[5, 4],
[0, 1, 3, 6]
]

Notes

Constraints:

• 1 <= number of nodes in the given tree <= 20000
• 0 <= node value < number of nodes
• Node values are unique

We have provided three solutions. We will be using depth-first search & breadth-first search, respectively, extracting the values of the nodes in the required order. In the last solution, we will solve the problem with a nice memory optimization trick.

Throughout the editorial, we will assume that there is node_count number of nodes in the binary tree.

Learn how to Construct the Binary Tree with the inorder and preorder traversal.

Binary Tree Level Order Traversal Solution 1: DSF

We will be maintaining a two-dimensional list to keep track of the nodes at every level.

Our approach will be:

• Initiate a DFS from the root node. All of the nodes in the binary tree will be visited exactly once during the DFS traversal.
• We will also track the level of the parameter node of the DFS function call. While moving from a parent to a child node, we will increase the level by 1.
• When a DFS for a node is initiated, we will store the value of that node in the appropriate position of our list. While initiating DFS for the child nodes from the parent node, we will initiate the call for the left child before the right child. It will ensure that we will get the nodes from left to right in our list.

Time Complexity

O(node_count), for dfs.

Auxiliary Space Used

O(node_count): There will be O(node_count) number of recursive calls on the call stack in the worst case.

Space Complexity

O(node_count)

Space used for input: O(node_count)

Auxiliary space used: O(node_count)

Space used for output: O(node_count)

So, total space complexity: O(node_count)

Know how to check if a binary tree is a Symmetric Tree or not.

Code for Binary Tree Level Order Traversal Solution 1: DSF

/*
* Asymptotic complexity in terms of total number of nodes in the given tree `n`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
void dfs(BinaryTreeNode *node, vector<vector> &ret, int level) {
   if (node == NULL) {
       return;
   }
   if (level >= (int)ret.size()) {
       // This node is the first encountered node of its level
       // So allocating memory for storing the nodes of this level.
       // Note that we would not need to insert more than one row because we must have already
       // allocated memory for storing nodes from every level between 0 to (level[node->value] - 1).
       ret.push_back(vector());
   }
   ret[level].push_back(node->value);
   // We would first explore the left child as we want to list the values from left to right
   dfs(node->left, ret, level + 1);
   dfs(node->right, ret, level + 1);
}
vector<vector> level_order_traversal(BinaryTreeNode *root) {
   vector<vector> ret;
   dfs(root, ret, 0);
   return ret;
}
</vector</vector</vector

‍

Know how to Validate a Binary Search Tree.

Binary Tree Level Order Traversal Solution 2: BFS

We will be maintaining a two-dimensional list to keep track of the nodes at every level in this solution too.

Our approach will be:

• Initiate a BFS from the root node. All of the nodes in the binary tree will be visited exactly once during the BFS traversal.
• We will also track the level of each visited node during the traversal. The level of a child node will be one more than the level of its parent node.
• When a node is popped from the queue, we will store the value of that node in the appropriate position of our list. While pushing the child nodes to the queue, we will push the left child before the right child in order to get the values from left to right in our list.

Time Complexity

O(node_count), for bfs.

Auxiliary Space Used

O(node_count)

For storing the levels of each node: O(node_count)

For the queue: O(node_count)

So, total auxiliary space complexity: O(node_count)

Space Complexity

O(node_count)

Space used for input: O(node_count)

Auxiliary space used: O(node_count)

Space used for output: O(node_count)

So, total space complexity: O(node_count)

Code for Binary Tree Level Order Traversal Solution 2: BFS

/*
* Asymptotic complexity in terms of total number of nodes in the given tree `n`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
void dfs(BinaryTreeNode *node, vector<vector> &ret, int level) {
   if (node == NULL) {
       return;
   }
   if (level >= (int)ret.size()) {
       // This node is the first encountered node of its level
       // So allocating memory for storing the nodes of this level.
       // Note that we would not need to insert more than one row because we must have already
       // allocated memory for storing nodes from every level between 0 to (level[node->value] - 1).
       ret.push_back(vector());
   }
   ret[level].push_back(node->value);
   // We would first explore the left child as we want to list the values from left to right
   dfs(node->left, ret, level + 1);
   dfs(node->right, ret, level + 1);
}
vector<vector> level_order_traversal(BinaryTreeNode *root) {
   vector<vector> ret;
   dfs(root, ret, 0);
   return ret;
}
</vector</vector</vector

Find out how to Build a Balanced BST from a Sorted Array.

Binary Tree Level Order Traversal Solution 2: BFS Memory Optimization

In order to reduce memory consumption, we can follow the below steps:

• Push the root node to the queue.
• Process all such nodes which come at the front of the queue and which are on the same level.
• After processing all such nodes, the queue would be filled up with nodes from the next level.
• Repeat the above process as long as there is a node yet to be visited. Note that in such a solution, we do not need to store the levels of each node in a separate array.

Time Complexity

O(node_count), for bfs.

Auxiliary Space Used

O(node_count)

For storing all the nodes from a level: O(node_count)

For the queue: O(node_count)

So, total auxiliary space complexity: O(node_count)

Space Complexity

O(node_count)

Space used for input: O(node_count)

Auxiliary space used: O(node_count)

Space used for output: O(node_count)

So, total space complexity: O(node_count)

Code for Binary Tree Level Order Traversal Solution 2: BFS Memory Optimization

/*
* Asymptotic complexity in terms of total number of nodes in the given tree `n`:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
vector<vector> level_order_traversal(BinaryTreeNode *root) {
   int max_node_count = 20000;
   queue<binarytreenode*> q;
   vector<vector> ret;
   vector level(max_node_count);
   q.push(root);
   level[root->value] = 0;
   while (!q.empty()) {
       auto node = q.front();
       q.pop();
       if (level[node->value] >= (int) ret.size()) {
           // This node is the first encountered node of its level
           // So allocating memory for storing the nodes of this level.
           // Note that we would not need to insert more than one row because we must have already
           // allocated memory for storing nodes from every level between 0 to (level[node->value] - 1).
           ret.push_back(vector());
       }
       ret[level[node->value]].push_back(node->value);
       // We would first push the left child to the queue as we want to list the values from left to right.
       if (node->left != NULL) {
           q.push(node->left);
           level[node->left->value] = level[node->value] + 1;
       }
       if (node->right != NULL) {
           q.push(node->right);
           level[node->right->value] = level[node->value] + 1;
       }
   }
   return ret;
}
</vector</binarytreenode*></vector

Learn how to find the Maximum Depth of a Binary Tree.

We hope that these solutions to the Binary Tree Level Order Traversal problem will help you level up your coding skills. Companies such as Amazon, D. E. Shaw & Co., Microsoft, Cisco, Samsung, Qualcomm, Morgan Stanley, etc., include Binary Tree Level Order Traversal interview questions in their tech interviews.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE Webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

To learn more, register for the FREE Webinar.