# Binary Tree Level Order Traversal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-tree-level-order-traversal)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-level-order-traversal
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [PhonePe](https://scaleengineer.com/companies/phonepe), [Gojek](https://scaleengineer.com/companies/gojek)
---
## Problem
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).

**Example 1:**

![](https://assets.glich.co/dsa/binary-tree-level-order-traversal/image0.jpg) 

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

**Example 2:**

**Input:** root = [1]
**Output:** [[1]]

**Example 3:**

**Input:** root = []
**Output:** []

**Constraints:**

* The number of nodes in the tree is in the range `[0, 2000]`.
* `-1000 <= Node.val <= 1000`

# Approaches
## Recursive Approach (Depth-First Search)
This approach uses a recursive helper function, which is a form of Depth-First Search (DFS), to traverse the tree. We pass the current node and its level as arguments to the function. The level number is used to determine which sublist in our result list the node's value should be added to.
**Time:** O(N) · **Space:** O(N)
**Pros:** The code can be very concise and is straightforward if one is comfortable with recursion.
**Cons:** It is not a natural way to solve a level-order problem, as DFS explores depth-wise.; For very deep trees, this approach can lead to a `StackOverflowError` due to deep recursion.
### Explanation
The core idea is to perform a preorder traversal (visiting the node, then its left child, then its right child) while keeping track of the current depth or level. We use a list of lists to store the result. When we visit a node at a certain `level`, we check if a list for that level already exists in our result list. If the `level` is equal to the current size of the result list, it means we are visiting this level for the first time, so we create a new list for it. Then, we add the node's value to the list corresponding to its level. The process is then repeated recursively for the left and right children at `level + 1`.

```java
/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, 0, result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // If this is the first time we are visiting this level, create a new list.
        if (level == result.size()) {
            result.add(new ArrayList<Integer>());
        }

        // Add the current node's value to the list for its level.
        result.get(level).add(node.val);

        // Recur for the left and right children.
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}
```
### Algorithm
- Initialize an empty list of lists, `result`.
- Define a helper function `dfs(node, level, result)`.
- In the main function, call `dfs(root, 0, result)` if the root is not null.
- Inside `dfs`:
  - If `node` is null, return.
  - If `level` equals `result.size()`, it means we're visiting this level for the first time. Add a new empty list to `result`.
  - Get the list for the current `level` from `result` and add `node.val` to it.
  - Recursively call `dfs` for the left child with `level + 1`.
  - Recursively call `dfs` for the right child with `level + 1`.
- Return `result`.

## Iterative Approach (Breadth-First Search)
This is the classic and most intuitive approach for level order traversal. It uses a queue data structure to process nodes in a breadth-first manner. We process the tree one level at a time, adding all nodes from a single level to the queue, and then processing them to find the nodes of the next level.
**Time:** O(N) · **Space:** O(N)
**Pros:** This is the canonical and most intuitive solution for this problem.; Being iterative, it avoids the risk of stack overflow for very deep trees.; It naturally processes the tree level by level, matching the problem's requirement.
**Cons:** May use slightly more memory than a DFS approach on a very narrow and deep (skewed) tree, although both have the same worst-case complexity.
### Explanation
We start by initializing a queue and adding the root node to it. The main logic is a `while` loop that continues as long as the queue is not empty. Inside this loop, we first determine the number of nodes at the current level by checking the queue's size. We then iterate that many times, dequeuing one node at a time, adding its value to a temporary list for the current level, and enqueuing its non-null children. After the inner loop finishes processing all nodes of the current level, the temporary list containing their values is added to our final result list. This process guarantees that we traverse the tree level by level from left to right.

```java
/**
 * 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            result.add(currentLevel);
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty list of lists, `result`.
- If `root` is null, return the empty `result`.
- Initialize a queue (e.g., `LinkedList`) and add the `root` to it.
- Start a `while` loop that runs as long as the queue is not empty.
  - Inside the loop, get the current size of the queue, `levelSize`.
  - Create a new list, `currentLevel`, to store the values of the nodes at the current level.
  - Loop `levelSize` times:
    - Dequeue a node from the queue.
    - Add the node's value to `currentLevel`.
    - If the node's left child is not null, enqueue it.
    - If the node's right child is not null, enqueue it.
  - After the inner loop, add `currentLevel` to `result`.
- Return `result`.

# Solutions
### Java

```java
/** * 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 < List < Integer >> levelOrder ( TreeNode root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } ans . add ( t ); } return ans ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[][]} */ var levelOrder =
  function (root) {
    let ans = [];
    if (!root) {
      return ans;
    }
    let q = [root];
    while (q.length) {
      let t = [];
      for (let n = q.length; n; --n) {
        const { val, left, right } = q.shift();
        t.push(val);
        left && q.push(left);
        right && q.push(right);
      }
      ans.push(t);
    }
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < vector < int >> levelOrder ( TreeNode * root ) { vector < vector < int >> ans ; if ( ! root ) return ans ; queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { vector < int > t ; for ( int n = q . size (); n ; -- n ) { auto node = q . front (); q . pop (); t . push_back ( node -> val ); if ( node -> left ) q . push ( node -> left ); if ( node -> right ) q . push ( node -> right ); } ans . push_back ( t ); } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def levelOrder ( self , root : Optional [ TreeNode ]) -> List [ List [ int ]]: ans = [] if root is None : return ans q = deque ([ root ]) while q : t = [] for _ in range ( len ( q )): node = q . popleft () t . append ( node . val ) if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) ans . append ( t ) return ans
```