Binary Tree Traversal Pattern | CodeTutor

Binary Tree Traversal

Easy

36 questions using this pattern

What is Binary Tree Traversal?

Visit all nodes in a binary tree in specific orders: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), or level-order (BFS). Each order reveals different structural information about the tree.

Think of it like this...

Imagine reading a family tree. Preorder is like announcing yourself first, then introducing your children. Inorder is alphabetical—left child, then you, then right child. Postorder is like calculating taxes—you need to know your children's totals before computing your own.

Another way to think about it: preorder is top-down (decisions flow from root to leaves), postorder is bottom-up (results bubble from leaves to root).

Core Concept

The three traversal orders differ only in when you process the current node relative to its children:

Preorder: Process before children → good for copying trees, prefix expressions
Inorder: Process between children → BST gives sorted order
Postorder: Process after children → good for deletion, evaluating expressions

The key insight is that these traversals naturally map to different problems:

Need to see parents before children? → Preorder
Need to aggregate child results? → Postorder
Need sorted BST elements? → Inorder
Need level-by-level? → BFS

Inorder Tree Traversal (Iterative)

Tree Traversal

def inorder_traversal(root):

    result = []

    stack = []

    curr = root

    while curr or stack:

        # Go left as far as possible

        while curr:

            stack.append(curr)

            curr = curr.left

        # Pop and process

        curr = stack.pop()

        result.append(curr.val)

        # Move to right subtree

        curr = curr.right

    return result

Variables

No variables yet

Binary Search Tree

Traversal Stack

empty

Problem

We have a binary search tree. Our goal is to visit all nodes in inorder (Left-Root-Right), which for a BST gives us sorted output.

1/26

Visual Walkthrough

Example tree:

Preorder (Root → Left → Right):

Visit 1 → Visit 2 → Visit 4 → Visit 5 → Visit 3
Result: [1, 2, 4, 5, 3]

Inorder (Left → Root → Right):

Visit 4 → Visit 2 → Visit 5 → Visit 1 → Visit 3
Result: [4, 2, 5, 1, 3]

For BST: gives elements in sorted order!

Postorder (Left → Right → Root):

Visit 4 → Visit 5 → Visit 2 → Visit 3 → Visit 1
Result: [4, 5, 2, 3, 1]

Children processed before parent—useful for computing heights/sizes.

Level-order (BFS):

Level 0: [1]
Level 1: [2, 3]
Level 2: [4, 5]
Result: [1, 2, 3, 4, 5]

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def preorder_recursive(root: TreeNode) -> list:
    """Preorder: Root → Left → Right"""
    if not root:
        return []
    return ([root.val]
            + preorder_recursive(root.left)
            + preorder_recursive(root.right))


def preorder_iterative(root: TreeNode) -> list:
    """Iterative preorder using stack."""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result


def inorder_recursive(root: TreeNode) -> list:
    """Inorder: Left → Root → Right"""
    if not root:
        return []
    return (inorder_recursive(root.left)
            + [root.val]
            + inorder_recursive(root.right))


def inorder_iterative(root: TreeNode) -> list:
    """Iterative inorder using stack."""
    result = []
    stack = []
    current = root

    while current or stack:
        # Go left as far as possible
        while current:
            stack.append(current)
            current = current.left

        # Process current node
        current = stack.pop()
        result.append(current.val)

        # Move to right subtree
        current = current.right

    return result


def postorder_recursive(root: TreeNode) -> list:
    """Postorder: Left → Right → Root"""
    if not root:
        return []
    return (postorder_recursive(root.left)
            + postorder_recursive(root.right)
            + [root.val])


def postorder_iterative(root: TreeNode) -> list:
    """Iterative postorder using two stacks."""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result[::-1]  # Reverse for postorder


def level_order(root: TreeNode) -> list[list]:
    """Level-order traversal using BFS."""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

Recognition Signals

Look for these keywords and patterns in problem descriptions:

binary treetree traversalpreorderinorderpostorderlevel orderserialize treeflatten treeBST to sortedkth smallest in BSTvalidate BSTpath sum

When to Use

Serializing/deserializing trees
Validating BST properties (inorder gives sorted order)
Computing tree properties (height, size, sum)
Copying or comparing trees
Path sum and path finding problems

Common Mistakes

Stack order in iterative preorder

Pushing left child before right child processes right first because stacks are LIFO.

Fix:

Push right child first, then left child:

if node.right:
    stack.append(node.right)  # Push right first
if node.left:
    stack.append(node.left)   # Left popped first

Iterative inorder is tricky

The iterative inorder traversal is harder to get right than preorder or postorder because you need to track when to go left vs when to process.

Fix:

Use the "go left until null, then process and go right" pattern:

while current or stack:
    while current:
        stack.append(current)
        current = current.left
    current = stack.pop()
    process(current)
    current = current.right

Pattern Variations

Morris Traversal

Inorder traversal using O(1) space by temporarily modifying the tree (threading right pointers to inorder successors).

Examples: Recover Binary Search Tree, Inorder without stack

Boundary Traversal

Traverse only the boundary of the tree: left boundary, leaves, right boundary in reverse.

Examples: Boundary of Binary Tree

Vertical Order Traversal

Group nodes by their horizontal distance from root. Nodes at same horizontal distance are in the same vertical line.

Examples: Vertical Order Traversal, Binary Tree Right Side View

Zigzag Level Order

Level-order but alternating direction: left-to-right, then right-to-left, and so on.

Examples: Binary Tree Zigzag Level Order Traversal

Tree Serialization

Use traversal order to convert tree to string and back. Preorder with null markers is common.

Examples: Serialize and Deserialize Binary Tree

Learning Path

1Warmup0/13

Start here to build foundational understanding.

Average of Levels in Binary Tree

#637Easy

Balanced Binary Tree

#110Easy

Binary Tree Inorder TraversalOptimal

#94Easy

Binary Tree Paths

#257Easy

Binary Tree Postorder Traversal

#145Easy

Binary Tree Preorder TraversalOptimal

#144Easy

Binary Tree Tilt

#563Easy

Diameter of Binary Tree

#543Easy

Insert into a Binary Search TreeOptimal

#701Easy

Invert Binary Tree

#226Easy

Maximum Depth of Binary Tree

#104Easy

Same Tree

#100Easy

Subtree of Another Tree

#572Easy

2Core Practice0/22

Master the pattern with these representative problems.

Add One Row to Tree

#623Medium

All Elements in Two Binary Search Trees

#1305Medium

Amount of Time for Binary Tree to Be Infected

#2385Medium

Balance a Binary Search TreeOptimal

#1382Medium

Binary Search Tree Iterator

#173Medium

Binary Search Tree to Greater Sum Tree

#1038Medium

Binary Tree Coloring Game

#1145Medium

Binary Tree Level Order Traversal

#102Medium

Binary Tree Level Order Traversal II

#107Medium

Binary Tree Pruning

#814Medium

Binary Tree Right Side View

#199Medium

Binary Tree Zigzag Level Order Traversal

#103Medium

Check Completeness of a Binary Tree

#958Medium

Construct Binary Tree from Preorder and Inorder Traversal

#105Medium

Convert BST to Greater Tree

#538Medium

Count Good Nodes in Binary Tree

#1448Medium

Delete Leaves With a Given Value

#1325Medium

Delete Node in a BSTOptimal

#450Medium

Kth Smallest Element in a BST

#230Medium

Lowest Common Ancestor of a Binary Search Tree

#235Medium

Minimum Height Trees

#310Medium

Validate Binary Search Tree

#98Medium

3Challenge0/1

Test your mastery with complex variations.

Serialize and Deserialize Binary Tree

#297Hard

Related Patterns

Explore similar techniques:

BFS (Breadth-First Search)

Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.

DFS (Depth-First Search)

Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.