Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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.

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.

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

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

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

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.

```
O(node_count), for dfs.
```

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

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

```
/*
* 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
```> &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> level_order_traversal(BinaryTreeNode *root) {
vector> ret;
dfs(root, ret, 0);
return ret;
}

*Know how to **Validate a Binary Search Tree**.*

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.

```
O(node_count), for bfs.
```

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

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

```
/*
* 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
```> &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> level_order_traversal(BinaryTreeNode *root) {
vector> ret;
dfs(root, ret, 0);
return ret;
}

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

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.

```
O(node_count), for bfs.
```

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

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

```
/*
* 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
```> level_order_traversal(BinaryTreeNode *root) {
int max_node_count = 20000;
queue q;
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;
}

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

Note: Input and Output will already be taken care of.

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.

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.

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

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

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

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.

```
O(node_count), for dfs.
```

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

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

```
/*
* 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
```> &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> level_order_traversal(BinaryTreeNode *root) {
vector> ret;
dfs(root, ret, 0);
return ret;
}

*Know how to **Validate a Binary Search Tree**.*

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.

```
O(node_count), for bfs.
```

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

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

```
/*
* 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
```> &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> level_order_traversal(BinaryTreeNode *root) {
vector> ret;
dfs(root, ret, 0);
return ret;
}

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

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.

```
O(node_count), for bfs.
```

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

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

```
/*
* 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
```> level_order_traversal(BinaryTreeNode *root) {
int max_node_count = 20000;
queue q;
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;
}

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

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs