Inorder, preorder, postorder and level order: which traversal for which problem

Short answer. Inorder, preorder and postorder are the three depth-first tree traversals. They differ only in when the root is visited: before, between or after its children. Level order is the breadth-first one, done with a queue. All four cost O(n). Below: which order fits which problem, Python code, and worked problems.

What are inorder, preorder and postorder?

A binary tree has nodes with a left and a right child. A traversal visits each node exactly once. Only the order changes.

Preorder: root, left subtree, right subtree. Inorder: left, root, right. Postorder: left, right, root. Level order: one level at a time.

The names follow the root's place. Pre means before the children, in means between, post means after.

Which traversal fits which problem?

Traversal	Order	Use when	Example
Preorder	Root, left, right	Copy or serialise a tree	Serialize Binary Tree
Inorder	Left, root, right	A search tree in sorted order	Kth Smallest in BST
Postorder	Left, right, root	A node's answer needs its children's	Height, diameter, delete
Level order	By levels	Anything about levels or depth	Level Order, Right Side View

The rule is short. Children before the parent: postorder. Levels: breadth-first. Most of the rest: preorder.

What do the orders look like on one tree?

Tree: root 1, left child 2, right child 3. Node 2 has children 4 and 5.

Preorder: 1, 2, 4, 5, 3. Inorder: 4, 2, 5, 1, 3. Postorder: 4, 5, 2, 3, 1. Level order: 1, 2, 3, 4, 5.

Notice inorder. Root 1 sits between the whole left subtree and the right one. That is why inorder lists a search tree in ascending order.

How do you write inorder and the others in Python?

from collections import deque

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

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # right first onto the stack
        if node.left: stack.append(node.left)     # so left comes out first
    return out

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                      # go left as far as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

def level_order(root):
    out, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):      # exactly one level
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        out.append(level)
    return out

The recursive form is shorter. The iterative form is for deep trees. Python recursion stops near a thousand frames.

When does a problem need a tree traversal?

• "Print values level by level", "right side view".
• "k-th smallest element in a BST."
• "Height", "diameter", "is it balanced".
• "Rebuild the tree from two traversals."

Almost every tree problem is a traversal plus work at each node. Pick the order first. Then decide what to do at the node.

How does postorder give height and diameter?

A node's height is one plus the larger child height. That is postorder: children first, then the node.

The diameter is the longest path between two nodes. At each node it equals left height plus right height. Compute heights recursively and update a global maximum on the way. One pass, O(n).

How does level order give Right Side View?

You need the nodes visible from the right. That is the last node of every level. Traverse by levels and take the last element of each. The whole solution is level_order plus one line.

How does inorder give the k-th smallest in a BST?

In a search tree, left is smaller and right is larger. Inorder lists values ascending. Run the iterative version with a stack and count popped nodes. The k-th pop is the answer. Stop there, the rest of the tree is not needed.

Time O(h + k), where h is the height. For small k that is far below O(n).

What mistakes break a traversal?

• Pushing the left child first in iterative preorder. The order flips.
• Not fixing the level size in breadth-first, so levels blend together.
• Skipping the empty tree check and reading root.left.
• Recursing on a million-node tree shaped like a chain.

How do you explain a traversal in an interview?

Name the order and why. Give O(n) time and O(h) memory, where h is the height. For level order the memory is O(w), the width of a level.

Asked for the iterative form, write inorder with a stack. It is the one they ask most.

Drill this pattern on the tree traversal page. The neighbouring pattern lives on the binary search tree page.

FAQ

How do you rebuild a tree from preorder and inorder?

The first preorder element is the root. Find it in inorder. Everything left of it is the left subtree. Everything right is the right one. Repeat for each part.

Can you traverse without a stack or recursion?

Yes, with Morris traversal. It temporarily rewires pointers and runs in O(1) memory. Interviews rarely ask for it.

How is a tree traversal different from a graph traversal?

A tree has no cycles, so no visited set is needed. Otherwise it is the same DFS and BFS.

Where do traversals show up in real systems?

Compilers evaluate a syntax tree in postorder. File systems compute folder sizes in postorder. UI frameworks render a component tree in preorder.