:orphan:

Binary Tree Inorder Traversal
=============================

.. highlight:: none

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

Given the ``root`` of a binary tree, return *the inorder traversal of
its nodes' values*.

 

**Example 1:**

.. container:: example-block

   **Input:** root = [1,null,2,3]

   **Output:** [1,3,2]

   **Explanation:**

   |image1|

**Example 2:**

.. container:: example-block

   **Input:** root = [1,2,3,4,5,null,8,null,null,6,7,9]

   **Output:** [4,2,6,5,7,1,3,9,8]

   **Explanation:**

   |image2|

**Example 3:**

.. container:: example-block

   **Input:** root = []

   **Output:** []

**Example 4:**

.. container:: example-block

   **Input:** root = [1]

   **Output:** [1]

 

**Constraints:**

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

 

**Follow up:** Recursive solution is trivial, could you do it
iteratively?

.. |image1| image:: https://assets.leetcode.com/uploads/2024/08/29/screenshot-2024-08-29-202743.png
.. |image2| image:: https://assets.leetcode.com/uploads/2024/08/29/tree_2.png

.. highlight:: python

Pattern
-------
Stack, Tree, Depth-First Search, Binary Tree

Solution
--------
For an inorder traversal, visit the left subtree, then the root, then the right
subtree recursively. ::

         root (2)
        /        \\
    left (1)  right (3)

Code
----

.. literalinclude:: ../problems/easy/binary-tree-inorder-traversal/binary_tree_inorder_traversal__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from binary_tree_inorder_traversal__approach_1 import inorderTraversal, TreeNode
>>> root = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
>>> inorderTraversal(root)
[1, 3, 2]
>>> root = None
>>> inorderTraversal(root)
[]
>>> root = TreeNode(1)
>>> inorderTraversal(root)
[1]

Complexity
----------
| :math:`n` is the number of nodes in the binary tree.
| Time: :math:`O(n)` — visit every node
| Auxiliary Space: :math:`O(1)`

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

.. autofunction:: binary_tree_inorder_traversal__approach_1.inorderTraversal