[Intermediate] — A university-level introduction to the binary tree traversal pattern: what it is, why it exists, how it works, and how to implement it independently.

Before you start

What you will be able to do after this lesson:

  1. Define preorder, inorder, and postorder traversal and explain when each is the right tool.
  2. Implement root-to-leaf path construction using preorder traversal.
  3. Implement a value that depends on children’s answers using postorder traversal.
  4. Explain why inorder traversal of a BST gives sorted values.

Study route: read the motivation and mechanism first, trace the worked example by hand, then attempt the independent task before looking at the hints.


1. Why this pattern exists (real-world motivation)

Imagine you’re building a file system browser. You need to display the directory structure as a tree. To build the display, you need to visit every directory and file in a specific order: you might want to list a directory before its contents (preorder), list contents before the directory summary (postorder), or list everything in alphabetical order (inorder for BSTs).

The mechanics of preorder/inorder/postorder are covered in traversal — this note is about recognizing when each order is the right tool, since that’s the part that actually shows up as a decision in interview problems.


2. Definitions and terminology

TermPlain-English definitionExample / analogy
PreorderProcess the current node before its childrenList a directory before its contents
InorderProcess the left subtree, then the current node, then the right subtreeList BST values in sorted order
PostorderProcess the children before the current nodeCompute a directory’s size after computing all subdirectory sizes
Root-to-leaf pathA path from the root node to a leaf nodeA file path from the root directory to a file

3. How it works — step by step

Preorder (root → left → right)

Use when you need to process/record a node before its children — e.g. building a path string from root to each leaf, since you need the ancestors already collected before you get to a leaf.

def binary_tree_paths(root):
    paths = []
    def dfs(node, path):
        if node is None:
            return
        path = path + [str(node.val)]
        if node.left is None and node.right is None:   # leaf
            paths.append("->".join(path))
            return
        dfs(node.left, path)
        dfs(node.right, path)
    dfs(root, [])
    return paths

This is preorder because path gets the current node appended before recursing into children — by the time you reach a leaf, path already holds the full chain of ancestors.

Postorder (left → right → root)

Use when a node’s answer depends on its children’s answers first — e.g. computing a max path sum through a subtree, which requires knowing the best path from each child before combining them at the parent.

def max_path_sum(root):
    best = float("-inf")
    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        left_gain = max(dfs(node.left), 0)     # ignore negative contributions
        right_gain = max(dfs(node.right), 0)
        best = max(best, node.val + left_gain + right_gain)   # combine children *after* recursing
        return node.val + max(left_gain, right_gain)           # what this node can contribute upward
    dfs(root)
    return best

Postorder because both children’s results (left_gain, right_gain) must be known before this node can compute anything.

Inorder (left → root → right)

Use when the tree is a BST and you need values in sorted order — e.g. finding the k-th smallest element. Inorder traversal of a BST visits nodes in ascending order because all values in the left subtree are less than the root, and all values in the right subtree are greater.


4. Implementation — complete runnable example

Runnable example: save as binary_tree_traversal_lab.py and run python3 binary_tree_traversal_lab.py. It uses only Python’s standard library and creates no external files.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def preorder(root):
    """Preorder traversal: root -> left -> right."""
    if not root:
        return []
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)    # process root
        dfs(node.left)             # traverse left
        dfs(node.right)            # traverse right
    dfs(root)
    return result
 
 
def inorder(root):
    """Inorder traversal: left -> root -> right."""
    if not root:
        return []
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)             # traverse left
        result.append(node.val)    # process root
        dfs(node.right)            # traverse right
    dfs(root)
    return result
 
 
def postorder(root):
    """Postorder traversal: left -> right -> root."""
    if not root:
        return []
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)             # traverse left
        dfs(node.right)            # traverse right
        result.append(node.val)    # process root
    dfs(root)
    return result
 
 
def binary_tree_paths(root):
    """Build all root-to-leaf paths."""
    paths = []
    def dfs(node, path):
        if node is None:
            return
        path = path + [str(node.val)]
        if node.left is None and node.right is None:   # leaf
            paths.append("->".join(path))
            return
        dfs(node.left, path)
        dfs(node.right, path)
    dfs(root, [])
    return paths
 
 
if __name__ == "__main__":
    # Build a sample tree:
    #       1
    #      / \
    #     2   3
    #    / \
    #   4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
 
    print("Preorder:", preorder(root))
    print("Inorder:", inorder(root))
    print("Postorder:", postorder(root))
    print("Binary tree paths:", binary_tree_paths(root))
 
    assert preorder(root) == [1, 2, 4, 5, 3]
    assert inorder(root) == [4, 2, 5, 1, 3]
    assert postorder(root) == [4, 5, 2, 3, 1]
    assert binary_tree_paths(root) == ["1->2->4", "1->2->5", "1->3"]
 
    print("binary_tree_traversal_lab: passed")

Expected output:

Preorder: [1, 2, 4, 5, 3]
Inorder: [4, 2, 5, 1, 3]
Postorder: [4, 5, 2, 3, 1]
Binary tree paths: ['1->2->4', '1->2->5', '1->3']
binary_tree_traversal_lab: passed

5. Complexity

O(n) — every node is visited exactly once regardless of the order.


6. Tradeoffs and limitations

  • Preorder is natural for copying a tree or building a path string.
  • Inorder is natural for BSTs where you need sorted output.
  • Postorder is natural when a node’s answer depends on its children’s answers.
  • Level-order (BFS) is natural when you need to process nodes level by level.

7. Check your understanding (self-assessment)

Attempt these without the note, then compare your reasoning below.

  1. Question: Given the tree above, trace through the preorder, inorder, and postorder traversals step by step.
  2. Question: Why does inorder traversal of a BST give sorted values?
  3. Question: When would you use postorder traversal instead of preorder?

Answers — after your attempt

  1. Preorder: 1, 2, 4, 5, 3 (root, left subtree, right subtree)
    Inorder: 4, 2, 5, 1, 3 (left subtree, root, right subtree)
    Postorder: 4, 5, 2, 3, 1 (left subtree, right subtree, root)
  2. In a BST, all values in the left subtree are less than the root, and all values in the right subtree are greater. Inorder visits left subtree first, then root, then right subtree — so values come out in ascending order.
  3. Use postorder when a node’s answer depends on its children’s answers first — e.g. computing a max path sum through a subtree, which requires knowing the best path from each child before combining them at the parent.

8. Practice — independent task

Task: Implement a function max_depth(root) that returns the maximum depth of a binary tree. Use postorder traversal. Test it with the following cases:

  • root = [3, 9, 20, null, null, 15, 7] → expected 3
  • root = [1, null, 2] → expected 2

Done when: your function returns the correct maximum depth for both test cases.


Practice problems

In the NeetCode 150 — solved and written up here:

  1. Binary Tree Level Order Traversal (LeetCode #102) — BFS — the traversal that is not a DFS order.
  2. Binary Tree Right Side View (LeetCode #199) — level order, keeping the last node of each level.
  3. Kth Smallest Element in a BST (LeetCode #230) — in-order is sorted for a BST; stop at .
  4. Validate Binary Search Tree (LeetCode #98) — in-order must be strictly increasing, or carry bounds down.
  5. Construct Tree from Preorder & Inorder (LeetCode #105) — the traversals as data rather than as a procedure.
  6. Serialize and Deserialize Binary Tree (LeetCode #297) — pre-order plus null markers is enough to rebuild the tree.
  7. Invert Binary Tree (LeetCode #226) — any traversal works, which is itself worth noticing.

Not in the NeetCode 150 — worth doing on LeetCode directly, since the 150 never asks for the three DFS orders iteratively, which is the useful exercise:

  1. Binary Tree Inorder Traversal (#94) — do it iteratively, with an explicit stack.
  2. Binary Tree Postorder Traversal (#145) — the awkward one to write iteratively; worth the struggle.
  3. Binary Tree Zigzag Level Order Traversal (#103) — level order with alternating direction.
  4. Vertical Order Traversal of a Binary Tree (#987) — traversal plus coordinate bookkeeping.
  5. Binary Tree Vertical Order Traversal (#314) — the simpler vertical variant; do it first.

Before moving on

You are done with this pattern when you can, closed-book:

  • State what pre-, in- and post-order each produce, and when each is the right choice.
  • Explain why in-order on a BST yields sorted output.
  • Implement all three traversals independently, iteratively for at least one.
  • Say which traversal you need when a node’s answer depends on its children’s.

Recap: The three depth-first orders differ only in when you visit the node relative to its subtrees. Pre-order works top-down when a node’s answer is needed before descending; post-order works bottom-up when the answer depends on the children; in-order on a BST produces sorted output. Choosing correctly is usually the whole problem.

Next: dfs-pattern — generalising tree traversal to arbitrary graphs, where you must additionally track what you have already visited.


10. Further reading

The pattern appears in many contexts beyond LeetCode:

  • File system navigation: Listing directory contents in different orders
  • Expression evaluation: Building and evaluating expression trees
  • Compiler design: Abstract syntax tree traversal
  • Game trees: Minimax algorithm for game playing

The core idea — choosing the right traversal order based on when you need to process each node — is a fundamental algorithmic technique that appears whenever you need to visit all nodes in a tree.

↑ Back to LeetCode Patterns — University-Style Teaching Notes