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
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 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 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 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.
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 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).
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.
| Preorder | Inorder | Postorder | |
|---|---|---|---|
| Order | Node, left, right | Left, node, right | Left, right, node |
| The tree here | 50, 30, 20, 40, 70, 60, 80 | 20, 30, 40, 50, 60, 70, 80 | 20, 40, 30, 60, 80, 70, 50 |
| The root | First | After its left subtree | Last |
| On a binary search tree | Not sorted in general | Always sorted | Not sorted in general |
| Time | O(n) | O(n) | O(n) |
| Extra space without recursion | One stack, O(h) | One stack, O(h) | Two stacks, O(n), or one, O(h) |
| Typical uses | Copying or saving a tree | Sorted keys, checking a search tree | Deleting a tree, sizes and heights |
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.
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.
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.
// 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.
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.
Preorder and inorder with one stack, postorder with two, level order with a queue, each in its own color.
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.
The recursive and the iterative version of preorder, inorder and postorder in all three languages, with a link to the full source on GitHub.
Six questions on preorder, eight on inorder and six on postorder, with an explanation for every option.
Binary Search Tree, AVL Tree and Red-Black Tree build the trees whose inorder is sorted, one insertion or deletion at a time.
// build your own
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