Pre-order, in-order, post-order and level order

Trees Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

For the tree 8, 3, 10, 1, 6, -, 14, what does this print?

Python 3.13
level = [8, 3, 10, 1, 6, None, 14]

def order(i: int, kind: str) -> list[int]:
    if i >= len(level) or level[i] is None:
        return []
    v = level[i]
    assert v is not None
    left, right = order(2 * i + 1, kind), order(2 * i + 2, kind)
    if kind == "pre":
        return [v] + left + right
    if kind == "in":
        return left + [v] + right
    return left + right + [v]

print(order(0, "in"), order(0, "post")[-1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 3, 6, 8, 10, 14] 8

Right: in-order of a search tree is sorted, and post-order ends at the root.

This tree is a search tree, so in-order gives sorted values, and every post-order walk finishes at the root.

Why not the others?
  • B [8, 3, 1, 6, 10, 14] 8. That is pre-order: the root comes first.
  • C [1, 3, 6, 8, 10, 14] 1. Post-order visits the root last, not first.
One tree, 8, 3, 10, 1, 6, 14, 4, 7, walked in four orders; pick an order to step through its visits.

Illustrative

Text version

preorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 1
  4. Visit 6
  5. Visit 4
  6. Visit 7
  7. Visit 10
  8. Visit 14

Result: [8, 3, 1, 6, 4, 7, 10, 14]. Order: 8, 3, 1, 6, 4, 7, 10, 14

inorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 1
  2. Visit 3
  3. Visit 4
  4. Visit 6
  5. Visit 7
  6. Visit 8
  7. Visit 10
  8. Visit 14

Result: [1, 3, 4, 6, 7, 8, 10, 14]. Order: 1, 3, 4, 6, 7, 8, 10, 14

postorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 1
  2. Visit 4
  3. Visit 7
  4. Visit 6
  5. Visit 3
  6. Visit 14
  7. Visit 10
  8. Visit 8

Result: [1, 4, 7, 6, 3, 14, 10, 8]. Order: 1, 4, 7, 6, 3, 14, 10, 8

level order:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 10
  4. Visit 1
  5. Visit 6
  6. Visit 14
  7. Visit 4
  8. Visit 7

Result: [8, 3, 10, 1, 6, 14, 4, 7]. Order: 8, 3, 10, 1, 6, 14, 4, 7

30-second answer

Pre-order visits a node before its children (copying or serialising a tree). In-order visits left, node, right (sorted output from a search tree). Post-order visits children first (sizes, heights, deleting a tree). Level order visits row by row with a queue (shortest depth, row questions). All are O(n).

Practise saying it · 60 s. No recording, just a timer

Compare the four traversal orders.

Say your answer out loud, then check which of these points you covered:

  • Pre, in, post: depth-first
  • Level order: queue
  • One job for each

Deep dive

Pre-, in- and post-order are depth-first and use O(h) stack; level order is breadth-first and uses O(w) queue space.

Any of the depth-first orders can be done iteratively with an explicit stack.

Pre-order plus in-order (with distinct values) is enough to rebuild a tree.

Common mistakes

  • Confusing in-order with 'left to right across a row'.
  • Using level order when a bottom-up answer (post-order) is needed.

Senior take & follow-ups

Tie each order to one job it does well. Memorised definitions alone do not score.

Follow-up questions

Think of your answer first, then open the hint.

  1. Which order serialises a tree so it can be rebuilt alone?

    Show hint

    Pre-order with markers for missing children.

  2. Why is post-order natural for heights?

    Show hint

    A node's height needs its children's heights first.

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.