Tree Traversals

    DSA · Beginner

    Definition

    Traversals visit every node: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root) and level order.

    Nearly every tree problem is a traversal with extra logic.

    Diagram

    12 ← 1 → 3pre 1 2 3 · in 2 1 …

    Flowchart

    Pick orderRecurse on childrenVisit root at the right timeUse a queue for level order

    Example: Three traversals

    t = (1, (2, None, None), (3, None, None))
pre = lambda n: [n[0]] + pre(n[1]) + pre(n[2]) if n else []
ino = lambda n: ino(n[1]) + [n[0]] + ino(n[2]) if n else []
post = lambda n: post(n[1]) + post(n[2]) + [n[0]] if n else []
print(pre(t), ino(t), post(t))

    Output: [1, 2, 3] [2, 1, 3] [2, 3, 1]

    Complexity

    O(n) time · O(h) stack

    Key points

    • Level order = BFS with a queue
    • Postorder suits height/size computations

    Interview questions

    Tree height?

    1 + max(height(left), height(right)), with empty = 0.

    More DSA topics

    ArraysLinked ListStackQueue