Binary Tree Traversals

Four ways to visit every node. Each ordering has distinct use-cases — inorder for sorted output, preorder for copying, postorder for deletion, level-order for BFS.

Time: O(n)

Space: O(h) DFS / O(w) BFS

Beginner

FastSlow

1/0

Visit order so far:

Inorder Code

Python

def inorder(node):
    if not node: return
    inorder(node.left)   # L
    visit(node)          # Root
    inorder(node.right)  # R
# Output for BST: sorted ascending

Expected Output

Inorder[4, 2, 8, 5, 1, 6, 3, 7]

Preorder[1, 2, 4, 5, 8, 3, 6, 7]

Postorder[4, 8, 5, 2, 6, 7, 3, 1]

Level Order[1, 2, 3, 4, 5, 6, 7, 8]

Quick Check

Inorder traversal of a BST produces nodes in what order?

1/3

Trees

Building your tree…

DSAverse

Binary Tree Traversals

Inorder Code

Expected Output

Quick Check

Binary Tree Traversals

Inorder Code

Expected Output

Quick Check