Inorder vs Preorder vs Postorder Traversal, step by step.

Inorder, preorder and postorder are the three depth-first traversals of a binary tree. All three visit every node once, in O(n) time, and differ only in when a node is visited: preorder before its two subtrees (node, left, right), inorder between them (left, node, right), postorder after them (left, right, node). Use preorder to copy a tree, inorder to read a binary search tree's keys in sorted order, and postorder to delete a tree or to compute something from the bottom up.

Below, all three walk the same tree of seven keys, and three different orders come out: the root first, the keys sorted, the root last.

Inorder vs preorder vs postorder: what differs

One tree, three orders

Take a binary search tree of seven keys: 50 at the root, 30 and 70 below it, and 20, 40, 60 and 80 at the bottom. Each traversal below starts at the root and visits every node once: it does with the node whatever the program needs, such as printing its key. The players ring each visited node and draw a line from it to the next one visited. Like the app, each traversal is iterative: it repeats the same few steps until no node is left, keeping the nodes still waiting on a stack. Which of the three lists the keys from the smallest to the largest?

Preorder on the seven-key tree

All steps as text
  1. Consider the iterative pre-order traversal. Use a stack to keep track of the nodes that need to be visited.
  2. Start with the root of the binary tree. Push this node onto the stack.
  3. Then pop the node (50) from the stack and visit it.
  4. First, push the right child of the visited node onto the stack.
  5. Then, push its left child onto the stack. After all children of the node (50) have been added, the next node (30) needs to be popped from the stack and visited.
  6. Pop the node (30) from the stack and visit it. Then repeat the procedure by pushing its child nodes onto the stack.
  7. Push the right child (40) onto the stack.
  8. Push the left child (20) onto the stack. Since all children of the node (30) have already been added, the next node (20) needs to be popped from the stack and visited.
  9. Pop the node (20) and visit it. Since it has no children, the next node (40) needs to be popped from the stack and visited.
  10. Pop the node (40) and visit it. Since it has no children, the next node (70) needs to be popped from the stack and visited.
  11. Pop the node (70) from the stack and visit it.
  12. Push the right child (80) onto the stack.
  13. Push the left child (60) onto the stack. Since all children of the node (70) have already been added, the next node (60) needs to be popped from the stack and visited.
  14. Pop the node (60) and visit it. Since it has no children, the next node (80) needs to be popped from the stack and visited.
  15. Pop the node (80) from the stack and visit it. If the stack is empty and this node has no descendants, it means that all nodes have already been visited, and the traversal is complete.
  16. Preorder visited the 7 nodes in the order 50, 30, 20, 40, 70, 60, 80. The root came first, and each node came before the nodes below it.
Inorder vs Preorder vs Postorder — Preorder on the seven-key tree. Last step: Preorder visited the 7 nodes in the order 50, 30, 20, 40, 70, 60, 80. The root came first, and each node came before the nodes below it.

Preorder visits a node before any node below it, so the root, 50, comes first, and the whole left subtree, 30, 20 and 40, comes before the right one. This is the order to copy a tree in: each node is made before its children are attached to it.

Inorder on the same tree

All steps as text
  1. Step through the iterative in-order traversal. Use a stack to manage the nodes to be visited.
  2. Start with the root of the tree. Push it onto the stack and apply the next rule. Rule 1: For each node pushed onto the stack, check for a left child. If it exists, push it onto the stack; if not, pop the next node from the stack and visit it.
  3. Push the node (30) onto the stack (according to Rule 1).
  4. Push the node (20) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  5. Pop and visit (20), the first node visited. Then Rule 2, for every visited node: if it has a right child, push that child and apply Rule 1 to it; if not, pop and visit the next node.
  6. Pop and visit (30). This node has a right child (40). It needs to be pushed onto the stack (Rule 2).
  7. Push the node (40) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  8. Pop and visit node (40). Again, apply Rule 2 by checking if it has a right child - there is none. Therefore, the next node at the top of the stack needs to be popped and visited.
  9. Pop and visit (50). This node has a right child (70). It needs to be pushed onto the stack (Rule 2).
  10. Push the node (70) onto the stack and check if it has a left child (Rule 1). Since the node (70) has a left child, this left child needs to be pushed onto the stack.
  11. Push the node (60) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  12. Pop and visit node (60) and check for the presence of a right child (Rule 2). There is none - therefore, the next node needs to be popped from the stack and visited.
  13. Pop and visit (70). This node has a right child (80). It needs to be pushed onto the stack (Rule 2).
  14. Push the node (80) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  15. Pop the node (80) from the stack and visit it. If this node does not have a right child and the stack is empty, it indicates that all nodes have already been visited. The traversal is complete.
  16. Inorder visited the 7 nodes in the order 20, 30, 40, 50, 60, 70, 80: from the smallest key to the largest, because this tree is a binary search tree.
Inorder vs Preorder vs Postorder — Inorder on the same tree. Last step: Inorder visited the 7 nodes in the order 20, 30, 40, 50, 60, 70, 80: from the smallest key to the largest, because this tree is a binary search tree.

Inorder visits a node after its whole left subtree and before its whole right subtree. In a binary search tree every key on the left is smaller and every key on the right larger, so the keys come out sorted. On a tree that is not a search tree, such as the app's default tree on the inorder page, they do not, which also makes inorder a test: a tree with distinct keys is a binary search tree exactly when its inorder is increasing.

Postorder on the same tree

All steps as text
  1. Take a closer look at how the post-order traversal algorithm works.
  2. Start at the root of the binary tree and push it onto the first stack.
  3. Then pop the node (50) from the first stack and push it onto the second stack. If this node has children, push its left and right children onto the first stack.
  4. Push the left child (30) onto the stack.
  5. Push the right child (70) onto the stack. After that, the next node needs to be popped from the first stack.
  6. Pop (70) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  7. Push the left child (60) onto the stack.
  8. Push the right child (80) onto the stack. After that, the next node needs to be popped from the first stack.
  9. Pop the node (80) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  10. Pop the node (60) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  11. Pop (30) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  12. Push the left child (20) onto the stack.
  13. Push the right child (40) onto the stack. After that, the next node needs to be popped from the first stack.
  14. Pop the node (40) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  15. Pop the node (20) from the first stack and push it onto the second stack. At this point the first stack is empty which means all nodes have been processed. The only thing left is to visit the nodes.
  16. Pop (20) from the second stack and visit it: the first node visited.
  17. Pop (40) from the second stack and visit it.
  18. Pop (30) and visit it.
  19. Pop (60) and visit it.
  20. Pop (80) and visit it.
  21. Pop (70) and visit it.
  22. Pop the root (50) and visit it. Both stacks are empty: the traversal is complete.
  23. Postorder visited the 7 nodes in the order 20, 40, 30, 60, 80, 70, 50. Each node came after the nodes below it, and the root came last.
Inorder vs Preorder vs Postorder — Postorder on the same tree. Last step: Postorder visited the 7 nodes in the order 20, 40, 30, 60, 80, 70, 50. Each node came after the nodes below it, and the root came last.

Postorder visits a node only after both of its subtrees, so the first visit is a leaf, 20, and the root, 50, comes last. This is the order to delete a tree in, since no node is removed before the nodes below it. The app gets it iteratively with two stacks: the first is the short one on the left, and the second, on the right, holds all seven nodes before the first visit.

One route, three moments

Written with recursion, where a function calls itself for the left and the right child, the three traversals differ in one line: where node.visit() stands. In pseudocode, with the names of the topic pages:

recursivePreOrder(node)
    if node is none
        return
    node.visit()
    recursivePreOrder(node.left)
    recursivePreOrder(node.right)

recursiveInOrder(node)
    if node is none
        return
    recursiveInOrder(node.left)
    node.visit()
    recursiveInOrder(node.right)

recursivePostOrder(node)
    if node is none
        return
    recursivePostOrder(node.left)
    recursivePostOrder(node.right)
    node.visit()

Each function reaches every node three times: on the way down, between its two subtrees, and on the way back up. Preorder visits on the first of these, inorder on the second, postorder on the third. The names say the same: the node comes before its subtrees, in between them, or after them. In short, NLR, LNR and LRN, where N is the node, L its left subtree and R its right one.

All three are depth-first: each finishes one subtree before it starts the next. Level order, the fourth traversal in the app, is breadth-first instead: it visits this tree level by level, 50, 30, 70, 20, 40, 60 and 80, with a queue. BFS vs DFS compares the two kinds.

Without recursion: one stack or two

Without recursion the three are no longer one function, which is why the three players work so differently. Preorder pushes the right child before the left, so that the left one comes off the stack first. Inorder pushes nodes down the left side until there are none, then pops and visits. Postorder takes two stacks: the first hands out the nodes in the order node, right, left, and the second gives them back reversed, left, right, node.

All three take O(n) time. Preorder and inorder keep at most about one node per level on their stack, O(h) for a tree of height h, as recursion does on the call stack. The two-stack postorder holds every node at once, O(n); a version with one stack brings it down to O(h).

Which traversal for which job

  • Preorder, the node before its subtrees: copying or saving a tree, so that every node can be rebuilt under a parent that already exists; listing folders with each folder above its contents.
  • Inorder, the node between its subtrees: the keys of a binary search tree in sorted order; checking whether a tree is a search tree; the k-th smallest key, by stopping after k visits.
  • Postorder, the node after its subtrees: deleting a tree; anything a node computes from its children, such as the size or the height of each subtree, or a folder's size from its contents; evaluating an arithmetic expression stored as a tree, where both operands come before their operator.

Rebuilding a tree from its traversals

Preorder and inorder together fix a binary tree with distinct keys. The preorder's first key, 50, is the root, and its place in the inorder splits the other keys into the left subtree, 20, 30 and 40, and the right one, 60, 70 and 80. The same split repeats inside each part. Postorder and inorder work the same way, with the root last.

Preorder and postorder together are not enough: a root with a single child gives the same two orders whether that child is on the left or on the right.

A binary search tree needs only its preorder or its postorder: insert the preorder into an empty tree, 50, 30, 20 and so on, or the postorder read backwards, and the same tree comes back. Its inorder says nothing about the shape: every search tree of these seven keys has the inorder 20 to 80, and inserting the keys in that order gives a chain seven levels tall, each node to the right of the last.

Inorder vs preorder vs postorder at a glance

PreorderInorderPostorder
OrderNode, left, rightLeft, node, rightLeft, right, node
The tree here50, 30, 20, 40, 70, 60, 8020, 30, 40, 50, 60, 70, 8020, 40, 30, 60, 80, 70, 50
The rootFirstAfter its left subtreeLast
On a binary search treeNot sorted in generalAlways sortedNot sorted in general
TimeO(n)O(n)O(n)
Extra space without recursionOne stack, O(h)One stack, O(h)Two stacks, O(n), or one, O(h)
Typical usesCopying or saving a treeSorted keys, checking a search treeDeleting a tree, sizes and heights

Common mix-ups

  • Postorder is preorder backwards. Not quite: postorder read backwards is node, right, left, here 50, 70, 80, 60, 30, 40, 20, while preorder is 50, 30, 20, 40, 70, 60, 80. Why two stacks still work.
  • Inorder is always sorted. Only on a binary search tree. On any binary tree, inorder lists the nodes from left to right as the tree is drawn; in a search tree that is also the order of the keys.
  • Level order is a fourth depth-first order. It is breadth-first, with a queue. Give its loop a stack instead, pushing the right child before the left, and it becomes the iterative preorder above.

Inorder, preorder and postorder interview questions

Which traversal of a binary search tree gives the keys in sorted order?

Inorder: left subtree, node, right subtree. Every key in the left subtree is smaller than the node and every key in the right one larger, so the keys come out from the smallest to the largest.

Which traversal is used to delete a tree?

Postorder: it visits a node only after both of its subtrees, so no node is deleted while the nodes below it still have to be reached through it.

Can a binary tree be rebuilt from its preorder and postorder?

Not in general: a node with a single child gives the same preorder and postorder whether the child is on the left or on the right. Preorder with inorder, or postorder with inorder, does fix a tree with distinct keys.

Seven keys here.
Your own tree in the app.

In VisiGrab, preorder, inorder, postorder and breadth-first (level order) traversal are four topics, each with a message for every step, on the default tree or on one you build.

Your own tree

Custom opens a tree editor with room for 15 nodes: Set gives a node a key from 0 to 99, and Delete removes a node with everything below it.

Four traversals

Preorder and inorder with one stack, postorder with two, level order with a queue, each in its own color.

Why each order

Info dialogs say what each order is for: copying and saving a tree for preorder, sorted keys and the search-tree check for inorder, deleting a tree for postorder.

Python, Java and C++

The recursive and the iterative version of preorder, inorder and postorder in all three languages, with a link to the full source on GitHub.

Three quizzes

Six questions on preorder, eight on inorder and six on postorder, with an explanation for every option.

Search trees to build

Binary Search Tree, AVL Tree and Red-Black Tree build the trees whose inorder is sorted, one insertion or deletion at a time.

Before, between, after,
on your own tree.

Download VisiGrab to build a binary tree of your own and step through preorder, inorder, postorder and level order on it.

The four tree traversals are topics among 30+. See them all