# Binary Tree Level Order Traversal

## Question ([LC.102](https://leetcode.com/problems/binary-tree-level-order-traversal/))

> Given a binary tree, return thelevel ordertraversal of its nodes' values. From left to right, level by level.

## Example

```
    3
   / \
  9  20
    /  \
   15   7
Output: [ [3], [9, 20], [15, 7] ]
```

## Analysis

We need to do a breadth-first search on a binary tree. Should be pretty standard. Create `List<List<Integer>> results` to hold the results and at each level create `List<Integer> level` to hold values at that level.

## Code 1

```java
public void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }

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

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        System.out.println(current.val);
        if (current.left != null) {
            queue.offer(current.left);
        }
        if (current.right != null) {
            queue.offer(current.right);
        }
    }
}
```

Note: `Queue` is an interface in Java. Instantiating an interface doesn't make sense. Instead we want to choose an existing collection implementation.

Note2: `ArrayDeque` is another option. It uses a circular linked list to store the nodes. And resize when necessary.

## Code 2

Now we can print out the nodes in level order. But how do we separate them by their respecting levels? We need to figure out the size at each level.

```java
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) {
        return results;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> level;
    queue.offer(root);
    TreeNode current;
    while (!queue.isEmpty()) {
        level = new ArrayList<>();
        // level size changes after enqueue and dequeue
        // so we have to store this outside of the loop
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            current = queue.poll();
            level.add(current.val);
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }                
        }
        results.add(level);
    }
    return results;
}
```

```python

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    
    results: List[List[int]] = []
    
    if root == None:
        return results 
    
    queue: Deque[root] = deque()
    queue.append(root)
    
    while len(queue) > 0:
        level_size = len(queue)
        level_result: List[int] = []
        for i in range(level_size):
            cur_node = queue.popleft()
            level_result.append(cur_node.val)
            if cur_node.left:
                queue.append(cur_node.left)
            if cur_node.right:
                queue.append(cur_node.right)
        results.append(level_result)
    return results 

```

## Follow Up ([LC.107](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/))

> Given a binary tree, return the bottom-up level order traversal of its nodes' values. From left to right, level by level from leaf to root.

## Example

```
    3
   / \
  9  20
    /  \
   15   7
 Output: [ [15, 7], [9, 20], [3] ]
```

## Analysis

Either add in the level to the front of the list `results.add(0, level)` or reverse the results before return it `Collections.reverse(results)`.

## References

[ArrayDeque](http://www.csc.csudh.edu/jhan/Fall2007/csc311/Projects/ArrayDeque.htm) Implementation by Jack Han


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/bfs/binary-tree-level-order-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.