Binary Tree Inorder Traversal

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:

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

Output: [1,3,2]

Explanation:

Example 2:

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:

Example 3:

Input: root = []

Output: []

Example 4:

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?

Pattern

Stack, Tree, Depth-First Search, Binary Tree

Approaches

Recursive

Explanation

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

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

Code

class TreeNode:
    """Node in a binary tree."""

    def __init__(self, val, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right


def inorderTraversal(root: TreeNode | None) -> list[int]:
    """Traverse a binary tree in order from left to right."""
    if root is None:
        return []
    else:
        return (
            inorderTraversal(root.left)
            + [root.val]
            + inorderTraversal(root.right)
        )

Test

>>> from binary_tree_inorder_traversal__recursive 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

\(n\) is the number of nodes in the binary tree, and \(d\) is the maximum depth of the tree

Measure	Complexity	Notes
Time	\(O(n)\)	visit every node
Auxiliary Space	\(O(d)\)	recursive call stack

class binary_tree_inorder_traversal__recursive.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

binary_tree_inorder_traversal__recursive.inorderTraversal(root: TreeNode | None) → list[int]

Traverse a binary tree in order from left to right.