Preorder, inorder, and postorder traversals

Problem¶

Define preorder, inorder, and postorder traversals. Provide an implementation in Python

Definitions¶

Preorder
- Visit root, then left, then right.
Inorder
- Visit left, then root, then right.
Postorder
- Visit left, then right, then root.

Difference¶

Preorder
- Good for copying/serializing tree structure.
Inorder
- On BST, returns sorted order.
Postorder
- Good for deleting/freeing tree or computing from children upward.

Example¶

    2
   / \
  1   3

Preorder
- 2, 1, 3
Inorder
- 1, 2, 3
Postorder
- 1, 3, 2

Key trick¶

The only difference is where you place the root visit relative to recursive calls.

Trap¶

Mixing the orders; interviewers often ask specifically why inorder is special for BSTs.

Idiomatic Python¶

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

Pytest¶

import pytest
from dataclasses import dataclass

@dataclass
class Node:
    val: int
    left: "Node | None" = None
    right: "Node | None" = None

@pytest.mark.parametrize(
    "root, expected_pre, expected_in, expected_post",
    [
        (
            Node(2, Node(1), Node(3)),
            [2, 1, 3],
            [1, 2, 3],
            [1, 3, 2],
        ),
        (
            Node(1, Node(2, Node(4)), Node(3)),
            [1, 2, 4, 3],
            [4, 2, 1, 3],
            [4, 2, 3, 1],
        ),
    ],
)
def test_tree_traversals(root, expected_pre, expected_in, expected_post):
    assert preorder(root) == expected_pre
    assert inorder(root) == expected_in
    assert postorder(root) == expected_post