:orphan:

Binary Tree Level Order Traversal
=================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/binary-tree-level-order-traversal/

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

|image1|

::


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

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg

.. highlight:: python

Pattern
-------
Tree, Breadth-First Search, Binary Tree

Solution
--------
A level order traversal is a breadth-first traversal of a binary tree. Track
all the nodes in the current level and add their values to the traversal. At
the same time, add their children to the next level. We finish traversing once
all the chilren are ``None``.

Code
----

.. literalinclude:: ../problems/medium/binary-tree-level-order-traversal/binary_tree_level_order_traversal__approach_1.py
    :language: python
    :lines: 15-

Test
----
>>> from binary_tree_level_order_traversal__approach_1 import levelOrder, TreeNode
>>> root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
>>> levelOrder(root)
[[3], [9, 20], [15, 7]]
>>> root = TreeNode(1)
>>> levelOrder(root)
[[1]]
>>> root = None
>>> levelOrder(root)
[]

Complexity
----------
| :math:`n` is the number of nodes in the binary tree
| Time: :math:`O(n)` — visit each node once
| Auxiliary Space: :math:`O(n)` — `next_level` holds one level of nodes, up to
:math:`O(n / 2)` for a full binary tree

.. autoclass:: binary_tree_level_order_traversal__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: binary_tree_level_order_traversal__approach_1.levelOrder