LeetCode 94 · Trees · DFS

Binary Tree Inorder Traversal, explained with a picture

Reading a family tree left, parent, right.

Trees · DFS
▶ Watch it step by step

The problem

Return a binary tree’s values in inorder: left subtree, node, right subtree.

Input:  [1, 2, 3, 4, 5, null, 6]
Output: [4, 2, 5, 1, 3, 6]

Picture it

Picture reading a family tree from left to right: before you write a person, you finish everyone on their left side; after writing them, you do their right side. A stack remembers where to come back to.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Iterative or recursive inorder walk. O(n).

Python solution

def inorder(root):
    out = []
    def walk(node):
        if not node:
            return
        walk(node.left)
        out.append(node.val)
        walk(node.right)
    walk(root)
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.