LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Binary tree traversals, visualized

Inorder, preorder and level-order traversals visit the same nodes; only the order differs. For the recursive ones, the difference is literally where one line sits.

How it works
Python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def inorder(node, out):
    if node is None:
        return out
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
    return out


def preorder(node, out):
    if node is None:
        return out
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
    return out


def levelorder(node, out):
    queue = [node]
    while queue:
        current = queue.pop(0)
        out.append(current.val)
        if current.left is not None:
            queue.append(current.left)
        if current.right is not None:
            queue.append(current.right)
    return out


root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

print("in   ", inorder(root, []))
print("pre  ", preorder(root, []))
print("level", levelorder(root, []))

How tree traversal works

Preorder records a node before recursing into its children. Inorder records it between the left and right calls — which, on a binary search tree, produces the values in sorted order. Postorder, not shown here, records it after both. Level-order is a different kind of traversal: it uses a queue instead of recursion and visits the tree row by row.

The example tree has root 4, children 2 and 6, and 2’s children 1 and 3. Inorder gives [1, 2, 3, 4, 6], preorder [4, 2, 1, 3, 6] and level-order [4, 2, 6, 1, 3].

What to watch for when it runs

  1. The output list grows one value at a time, so you can see exactly when each node is visited.
  2. During the recursive traversals the call stack mirrors the path from the root to the current node.
  3. During level-order, the queue holds the next row of the tree.

Time and space complexity

Time
O(n) each
Space
O(h) for recursion, O(w) for level-order

h is the tree’s height and w its widest level. Every node is visited exactly once by every traversal.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.