Tree Traversals (Inorder, Preorder, Postorder)

Table of Contents +

You have a tree full of nodes. Now you want to do something with every single node. Maybe print all the values. Maybe add them up. The problem is that a tree is not a straight line like an array. So in what order do you visit the nodes? That order is what we call a traversal. A traversal is just a fixed rule for visiting every node in a tree exactly once.

In this tutorial we will learn the three most common traversals. They all go deep into the tree first. So we call them depth-first traversals. The three are preorder, inorder, and postorder.

🌳 Our Example Tree

Let’s use one small tree for everything. The same tree every time. That way you can really see how only the order changes.

1

2

3

4

5

So node 1 is the root. The root is the top node. It is the one with no parent above it. Node 1 has two children, 2 and 3. Then node 2 has its own two children, 4 and 5. Nodes 3, 4, and 5 have no children. A node with no children is called a leaf.

Keep this picture in your head. We will visit these same five nodes in three different orders.

🎯 The Three Orders

Every node has three things around it. There is the node itself. There is its left side. And there is its right side. The only difference between the three traversals is when we visit the node itself.

Here is the simple rule for each one.

Traversal Order it follows When we visit the node
Preorder Root, Left, Right First, before its children
Inorder Left, Root, Right In the middle, between its two sides
Postorder Left, Right, Root Last, after its children

See the pattern? The word “order” stays. Only the prefix changes. Pre means the root comes before. In means the root comes in between. Post means the root comes after. That prefix tells you exactly where the root goes.

Tip

Here is a trick to remember it. Look only at where the root sits. Pre means root first. In means root in the middle. Post means root last. The left side is always visited before the right side in all three.

🔁 Why Recursion Fits So Well

Think about what a tree really is. The root has a left child. That left child is itself the root of a smaller tree. And its left child is the root of an even smaller tree. A tree is made of smaller trees inside it. We call this self-similar shape a recursive structure.

So the natural way to walk a tree is recursion. Recursion means a function that calls itself on a smaller piece of the same problem.

Here is the idea in plain words. To traverse any node, we do the same three jobs:

  • Visit the node itself, which means print it.
  • Traverse its whole left side the same way.
  • Traverse its whole right side the same way.

The only thing we move around is when the “visit the node itself” step happens. Put it first and you get preorder. Put it in the middle and you get inorder. Put it last and you get postorder.

Every recursion needs a stopping point, or it runs forever. Our stopping point is simple. If the node is empty, meaning there is nothing there, we just stop and go back. That empty case is the base case.

🪜 Steps to Traverse the Tree

Let’s write the steps for each order on our example tree. Read them slowly and follow the picture.

Preorder (Root, Left, Right):

  1. Visit the current node.
  2. Go do a full preorder on the left child.
  3. Then go do a full preorder on the right child.
  4. If the node is empty, stop.

On our tree this gives: 1, 2, 4, 5, 3.

Inorder (Left, Root, Right):

  1. Go do a full inorder on the left child first.
  2. Then visit the current node.
  3. Then go do a full inorder on the right child.
  4. If the node is empty, stop.

On our tree this gives: 4, 2, 5, 1, 3.

Postorder (Left, Right, Root):

  1. Go do a full postorder on the left child.
  2. Then go do a full postorder on the right child.
  3. Then visit the current node last.
  4. If the node is empty, stop.

On our tree this gives: 4, 5, 2, 3, 1.

Note

Notice that the left side (nodes 4, 2, 5) is always finished before the right side (node 3) in every order. The right child of the root, node 3, shows up near the end each time. Only the position of each root changes.

💻 The Code in 5 Languages

Now let’s build the same tree in code and run all three traversals on it. We make a small node type. We link the five nodes together. Then we write one function per order. Each function calls itself on the left and right children. Watch where the print line sits in each function. That single line is the whole difference.

tree_traversals.py
# A single tree node: a value plus links to left and right children
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


# Preorder: visit Root, then Left, then Right
def preorder(node):
    if node is None:                # base case: empty node, stop
        return
    print(node.value, end=" ")      # visit the node first
    preorder(node.left)             # then the whole left side
    preorder(node.right)            # then the whole right side


# Inorder: visit Left, then Root, then Right
def inorder(node):
    if node is None:
        return
    inorder(node.left)              # left side first
    print(node.value, end=" ")      # then the node, in the middle
    inorder(node.right)             # then the right side


# Postorder: visit Left, then Right, then Root
def postorder(node):
    if node is None:
        return
    postorder(node.left)            # left side
    postorder(node.right)           # right side
    print(node.value, end=" ")      # node last


# Build the example tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)


print("Preorder: ", end=" ")
preorder(root)
print()


print("Inorder:  ", end=" ")
inorder(root)
print()


print("Postorder:", end=" ")
postorder(root)
print()

The output of the above code will be:

Preorder:  1 2 4 5 3
Inorder:   4 2 5 1 3
Postorder: 4 5 2 3 1

Look at the three functions side by side. The body is the same three lines every time. The print line just moves. That is the whole secret.

Output

Preorder gives 1 2 4 5 3. Inorder gives 4 2 5 1 3. Postorder gives 4 5 2 3 1. Same tree, three different orders, just by moving where we print the node.

⏱️ How Fast Is It?

Each traversal touches every node one time. Not more, not less. So if the tree has n nodes, we do n visits. That makes the time O(n). The work grows in a straight line with the number of nodes.

There is also some memory cost from recursion. Each recursive call sits and waits on a call stack until the deeper calls finish. The deepest the stack ever gets is the height of the tree, which we write as h. So the extra memory is O(h).

Note

For a balanced tree the height h is about O(log n), so the memory stays small. But for a tree that leans all to one side like a long chain, the height becomes O(n). Then the stack can get that deep too.

Here is the full picture for all three traversals.

Traversal Time Extra Space
Preorder O(n) O(h)
Inorder O(n) O(h)
Postorder O(n) O(h)

⚠️ Common Mistakes

A few mistakes catch almost everyone at the start. Watch for these.

  • Forgetting the base case. If you never check for the empty node, the function keeps calling itself and the program crashes. Always start with the “if node is empty, stop” line.
  • Mixing up left and right order. In all three traversals the left side is visited before the right side. Swap them by accident and your output is wrong.
  • Putting the print line in the wrong spot. The print line is the only thing that moves. Top for preorder, middle for inorder, bottom for postorder. Get that one line right and you are done.
  • Thinking inorder always gives sorted values. It only comes out sorted for a binary search tree, where left is smaller and right is bigger. On a plain tree, inorder is just left, root, right.

🧩 What You’ve Learned

✅ A traversal is a fixed rule for visiting every node in a tree exactly once.

✅ The three depth-first orders are preorder (Root, Left, Right), inorder (Left, Root, Right), and postorder (Left, Right, Root).

✅ Only one thing changes between them: when you visit the node itself, before, between, or after its children.

✅ These traversals are naturally recursive, with the empty node as the base case that stops the recursion.

✅ Each traversal runs in O(n) time because it visits every node once, and uses O(h) extra space for the call stack.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In a preorder traversal, when is the current node visited?

    Why: Preorder means Root, Left, Right, so the node is visited first, before its children.

  2. 2

    For the example tree (root 1, with children 2 and 3, and 2 having children 4 and 5), what is the inorder output?

    Why: Inorder is Left, Root, Right: the left subtree gives 4 2 5, then root 1, then right 3.

  3. 3

    Why are these traversals a natural fit for recursion?

    Why: A tree is a self-similar structure, so each child is itself the root of a smaller tree we traverse the same way.

  4. 4

    What is the time complexity of any of these traversals on a tree with n nodes?

    Why: Each node is visited exactly once, so the total work grows linearly as O(n).

Score: 0 / 4

🚀 What’s Next?

Previous Binary Tree Next Level Order Traversal (BFS)

Share & Connect

Share on LinkedIn