15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
They are the three depth-first ways to visit every node of a binary tree once. Each finishes one subtree before the other, and only the moment you process the current node changes: preorder is node, left, right, inorder is left, node, right, and postorder is left, right, node. Each runs in O(n) time.
| Preorder | Node, left, right: [A, B, D, E, C] |
|---|---|
| Inorder | Left, node, right: [D, B, E, A, C] |
| Postorder | Left, right, node: [D, E, B, C, A] |
| Time | O(n) for all three |
| Extra space | O(h) recursion stack, h is the tree height |
A binary tree node has:
A child reference can be null, meaning that subtree is empty.
Assume you can identify a tree’s root, left subtree, and right subtree. Every recursive traversal call receives the root of one subtree.
Depth-first traversal goes down one subtree as far as possible before moving to another subtree. When both children exist, visit the left subtree before the right subtree.
Produce one output value for every non-null node.
Use this tree throughout the lesson:
1 A
2 / \
3 B C
4 / \
5 D EIts links are:
1A.left = B A.right = C
2B.left = D B.right = E
3C.left = null C.right = null
4D.left = null D.right = null
5E.left = null E.right = nullThe three depth-first traversals differ in where they process the current node.
| Traversal | Order within one subtree rooted at node | Output on this tree |
|---|---|---|
| Preorder | node, left, right | [A, B, D, E, C] |
| Inorder | left, node, right | [D, B, E, A, C] |
| Postorder | left, right, node | [D, E, B, C, A] |
Start with preorder. Its rule is:
“Process” means append the node’s value to the output list.
The call stack remembers parent calls that are not finished yet. While the traversal is inside D, the calls for A and B remain active because they still have work to finish.
| State | Active action | Output after processing | What happens next |
|---|---|---|---|
| 0 | Begin preorder(A); process A | [A] | Enter A’s left subtree at B. |
| 1 | Enter preorder(B); process B | [A, B] | Enter B’s left subtree at D. |
| 2 | Enter preorder(D); process D | [A, B, D] | D’s left and right children are null, so both calls return immediately. |
| 3 | Return to B, then enter preorder(E); process E | [A, B, D, E] | E’s null children return immediately. |
| 4 | Return to A, then enter preorder(C); process C | [A, B, D, E, C] | C’s null children return immediately. |
| 5 | All calls return | [A, B, D, E, C] | Moving the processing action gives inorder [D, B, E, A, C] and postorder [D, E, B, C, A]. |
At State 2, the active call path is:
Preorder visits A, B, D, E, C. While D runs, the calls for A and B are still waiting, so the active call path is A, B, D.
D has no child to explore. Its calls on null return immediately. Control resumes in B, which still needs to traverse its right subtree. That is why E comes after D.
Consider one traversal call, such as the call on B.
When that call finishes, it must have placed every non-null node in B’s subtree into the output exactly once. It must also place them in that traversal’s required order.
For preorder(B), B’s subtree produces:
1[B, D, E]For inorder(B), it produces:
1[D, B, E]For postorder(B), it produces:
1[D, E, B]The invariant is:
For any traversal call on subtree root
r, when that call returns, the output contains every non-null node inr’s subtree exactly once in that traversal’s specified relative order.
The invariant includes empty subtrees. A call on null adds nothing and returns. Its subtree has no non-null nodes, so the required output is empty.
Each traversal starts with the same decision:
1Is this subtree empty?If it is empty, return before reading a value or child pointer.
Otherwise, every traversal must do three pieces of work:
Only the position of processing changes.
Process first:
1node, left, rightFor A, emit A before entering B or C.
Process between the child traversals:
1left, node, rightFor A, finish B’s entire subtree before emitting A, then traverse C’s subtree.
Process last:
1left, right, nodeFor A, finish both B’s and C’s subtrees before emitting A.
The recursive calls use the call stack to remember what remains. An inorder call on A remembers that it must emit A and then traverse C after its call on B returns.
Assume this node contract:
1Node:
2 value // value stored at this node
3 left // Node or null
4 right // Node or nullEach public function returns a new list. The helper appends to the supplied output list. It does not change any node, child reference, or node value.
11 function preorder(root) -> List
22 output <- empty list
33 preorderVisit(root, output)
44 return output
55
66 procedure preorderVisit(node, output)
77 // node is a Node or null.
88 // Mutates output by appending values; does not mutate the tree.
99 if node = null
1010 return
1111
1212 append node.value to output
1313 preorderVisit(node.left, output)
1414 preorderVisit(node.right, output)11 function inorder(root) -> List
22 output <- empty list
33 inorderVisit(root, output)
44 return output
55
66 procedure inorderVisit(node, output)
77 // node is a Node or null.
88 // Mutates output by appending values; does not mutate the tree.
99 if node = null
1010 return
1111
1212 inorderVisit(node.left, output)
1313 append node.value to output
1414 inorderVisit(node.right, output)11 function postorder(root) -> List
22 output <- empty list
33 postorderVisit(root, output)
44 return output
55
66 procedure postorderVisit(node, output)
77 // node is a Node or null.
88 // Mutates output by appending values; does not mutate the tree.
99 if node = null
1010 return
1111
1212 postorderVisit(node.left, output)
1313 postorderVisit(node.right, output)
1414 append node.value to outputThe base case is always lines 9–10. Never read node.value, node.left, or node.right before that check.
Dry-run preorder(A) using the preorder pseudocode.
The initial call is:
1preorder(A)| Step | Executed line | Active call path | Output | Result |
|---|---|---|---|---|
| 1 | 2 | preorder(A) | [] | Create output. |
| 2 | 3 | preorder(A) → preorderVisit(A) | [] | Start visiting the root. |
| 3 | 9 | A | [] | A is not null. |
| 4 | 12 | A | [A] | Process A first. |
| 5 | 13 | A → B | [A] | Call preorderVisit(B). |
| 6 | 9 | A → B | [A] | B is not null. |
| 7 | 12 | A → B | [A, B] | Process B. |
| 8 | 13 | A → B → D | [A, B] | Call preorderVisit(D). |
| 9 | 9 | A → B → D | [A, B] | D is not null. |
| 10 | 12 | A → B → D | [A, B, D] | Process D. |
| 11 | 13, then 9–10 | A → B → D → null | [A, B, D] | D’s left child is null; return. |
| 12 | 14, then 9–10 | A → B → D → null | [A, B, D] | D’s right child is null; return. |
| 13 | 14 | A → B → E | [A, B, D] | D has returned. Call preorderVisit(E). |
| 14 | 9 | A → B → E | [A, B, D] | E is not null. |
| 15 | 12 | A → B → E | [A, B, D, E] | Process E. |
| 16 | 13, then 9–10 | A → B → E → null | [A, B, D, E] | E’s left child is null; return. |
| 17 | 14, then 9–10 | A → B → E → null | [A, B, D, E] | E’s right child is null; return. |
| 18 | 14 | A → C | [A, B, D, E] | B has returned. Call preorderVisit(C). |
| 19 | 9 | A → C | [A, B, D, E] | C is not null. |
| 20 | 12 | A → C | [A, B, D, E, C] | Process C. |
| 21 | 13, then 9–10 | A → C → null | [A, B, D, E, C] | C’s left child is null; return. |
| 22 | 14, then 9–10 | A → C → null | [A, B, D, E, C] | C’s right child is null; return. |
| 23 | 4 | preorder(A) | [A, B, D, E, C] | Return the completed list. |
Line 12 occurs before lines 13 and 14, so preorder emits each node before either child call.
For inorder, move the append to between the two recursive calls. For postorder, move it after both calls.
Use a structural argument over subtrees.
The claim is the invariant: when a traversal call returns for subtree root r, the output contains every non-null node in that subtree exactly once in the specified order.
Suppose node = null.
Each helper checks this condition on line 9 and returns on line 10. It appends no value and makes no further calls.
An empty subtree has no non-null nodes. Therefore the output receives every node from that subtree exactly once—there are none—and the required order is satisfied.
Suppose node is non-null. Assume the recursive calls correctly traverse its left and right subtrees.
node.value, line 13 correctly traverses the left subtree, and line 14 correctly traverses the right subtree. The resulting order is node, left subtree, right subtree.node.value, and line 14 correctly traverses the right subtree. The resulting order is left subtree, node, right subtree.node.value. The resulting order is left subtree, right subtree, node.The current node is emitted once. Each child call handles its own subtree once. The left and right subtrees are visited in a consistent left-before-right order.
Therefore, when the current call returns, it has produced every non-null node in its subtree exactly once in the required traversal order.
Every recursive call moves from a node to one of its children. A finite tree has only finitely many nodes, and child references eventually reach null. At null, the helper returns immediately. Therefore all calls return, including the original call on the root.
Let n be the number of non-null nodes and let h be the tree height.
For each non-null node:
So each of the n non-null nodes is entered and processed once.
There are also calls on null child references. Each null call performs a null check and returns, which is constant work. A binary tree has only a constant number of child references per node, so these null calls do not change the linear bound.
The total traversal time is:
1O(n)The bound applies to preorder, inorder, and postorder.
The recursion stack holds active calls along one root-to-leaf path.
At most one active call exists for each node on that path, so the auxiliary call-stack space is:
1O(h)For the five-node example, the deepest preorder path is:
1A → B → DThat path has three active non-null calls before D’s null-child calls return.
If the returned list is counted as output storage, it contains one value for each of the n non-null nodes:
1O(n) output storageThat output storage is separate from the O(h) auxiliary recursion-stack space.
Incorrect order:
1append node.value to output
2if node = null
3 returnSmallest exposing input:
1root = nullWrong result:
1Runtime error when attempting to read node.valueCorrection:
1if node = null
2 return
3append node.value to outputThe null check must happen before accessing the node’s value or children.
Incorrect preorder body:
1preorderVisit(node.left, output)
2append node.value to output
3preorderVisit(node.right, output)Smallest exposing input:
1 A
2 / \
3 B CWrong output:
1[B, A, C]Correction:
1append node.value to output
2preorderVisit(node.left, output)
3preorderVisit(node.right, output)Preorder is node, left, right.
Incorrect inorder body:
1inorderVisit(node.left, output)
2inorderVisit(node.right, output)
3append node.value to outputSmallest exposing input:
1 A
2 / \
3 B CWrong output:
1[B, C, A]Correction:
1inorderVisit(node.left, output)
2append node.value to output
3inorderVisit(node.right, output)Inorder is left, node, right.
Consider this tree:
1 5
2 / \
3 9 1Its inorder traversal is:
1[9, 5, 1]The wrong claim is that this output must be sorted.
The output is unsorted because this tree has no stated binary-search-tree ordering property. Inorder output is sorted only when a separate binary-search-tree ordering property holds.
| Input | Preorder | Inorder | Postorder |
|---|---|---|---|
| Empty tree | [] | [] | [] |
Single node A | [A] | [A] | [A] |
Left-only chain A → B → C | [A, B, C] | [C, B, A] | [C, B, A] |
Right-only chain A → B → C through right links | [A, B, C] | [A, B, C] | [C, B, A] |
Implement these functions:
1preorder(root)
2inorder(root)
3postorder(root)Each function must:
null,The executable tests will verify:
A, B, C, D, E,1class Node:
2 def __init__(self, value, left=None, right=None):
3 self.value, self.left, self.right = value, left, right
4
5def preorder(root):
6 out = []
7
8 def visit(node):
9 if node is None:
10 return
11 out.append(node.value) # node, left, right
12 visit(node.left)
13 visit(node.right)
14
15 visit(root)
16 return out
17
18def inorder(root):
19 out = []
20
21 def visit(node):
22 if node is None:
23 return
24 visit(node.left)
25 out.append(node.value) # left, node, right
26 visit(node.right)
27
28 visit(root)
29 return out
30
31def postorder(root):
32 out = []
33
34 def visit(node):
35 if node is None:
36 return
37 visit(node.left)
38 visit(node.right)
39 out.append(node.value) # left, right, node
40
41 visit(root)
42 return out
43
44root = Node("A", Node("B", Node("D"), Node("E")), Node("C"))
45print("preorder ", "[" + ", ".join(preorder(root)) + "]")
46print("inorder ", "[" + ", ".join(inorder(root)) + "]")
47print("postorder", "[" + ", ".join(postorder(root)) + "]")1import java.util.ArrayList;
2import java.util.List;
3
4public class Main {
5 static class Node {
6 String value;
7 Node left, right;
8 Node(String value, Node left, Node right) { this.value = value; this.left = left; this.right = right; }
9 Node(String value) { this(value, null, null); }
10 }
11
12 static void preorder(Node node, List<String> out) {
13 if (node == null) return;
14 out.add(node.value); // node, left, right
15 preorder(node.left, out);
16 preorder(node.right, out);
17 }
18
19 static void inorder(Node node, List<String> out) {
20 if (node == null) return;
21 inorder(node.left, out);
22 out.add(node.value); // left, node, right
23 inorder(node.right, out);
24 }
25
26 static void postorder(Node node, List<String> out) {
27 if (node == null) return;
28 postorder(node.left, out);
29 postorder(node.right, out);
30 out.add(node.value); // left, right, node
31 }
32
33 public static void main(String[] args) {
34 Node root = new Node("A", new Node("B", new Node("D"), new Node("E")), new Node("C"));
35 List<String> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();
36 preorder(root, pre);
37 inorder(root, in);
38 postorder(root, post);
39 System.out.println("preorder " + pre);
40 System.out.println("inorder " + in);
41 System.out.println("postorder " + post);
42 }
43}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct Node {
7 string value;
8 Node *left, *right;
9 Node(string v, Node* l = nullptr, Node* r = nullptr) : value(v), left(l), right(r) {}
10};
11
12void preorder(Node* node, vector<string>& out) {
13 if (!node) return;
14 out.push_back(node->value); // node, left, right
15 preorder(node->left, out);
16 preorder(node->right, out);
17}
18
19void inorder(Node* node, vector<string>& out) {
20 if (!node) return;
21 inorder(node->left, out);
22 out.push_back(node->value); // left, node, right
23 inorder(node->right, out);
24}
25
26void postorder(Node* node, vector<string>& out) {
27 if (!node) return;
28 postorder(node->left, out);
29 postorder(node->right, out);
30 out.push_back(node->value); // left, right, node
31}
32
33string fmt(const vector<string>& v) {
34 string s = "[";
35 for (size_t i = 0; i < v.size(); i++) s += (i ? ", " : "") + v[i];
36 return s + "]";
37}
38
39int main() {
40 Node d("D"), e("E"), c("C");
41 Node b("B", &d, &e);
42 Node root("A", &b, &c);
43 vector<string> pre, in, post;
44 preorder(&root, pre);
45 inorder(&root, in);
46 postorder(&root, post);
47 cout << "preorder " << fmt(pre) << endl;
48 cout << "inorder " << fmt(in) << endl;
49 cout << "postorder " << fmt(post) << endl;
50}1class Node {
2 constructor(value, left = null, right = null) {
3 this.value = value;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function preorder(node, out = []) {
10 if (node === null) return out;
11 out.push(node.value); // node, left, right
12 preorder(node.left, out);
13 preorder(node.right, out);
14 return out;
15}
16
17function inorder(node, out = []) {
18 if (node === null) return out;
19 inorder(node.left, out);
20 out.push(node.value); // left, node, right
21 inorder(node.right, out);
22 return out;
23}
24
25function postorder(node, out = []) {
26 if (node === null) return out;
27 postorder(node.left, out);
28 postorder(node.right, out);
29 out.push(node.value); // left, right, node
30 return out;
31}
32
33const root = new Node('A', new Node('B', new Node('D'), new Node('E')), new Node('C'));
34const fmt = (a) => `[${a.join(', ')}]`;
35console.log(`preorder ${fmt(preorder(root))}`);
36console.log(`inorder ${fmt(inorder(root))}`);
37console.log(`postorder ${fmt(postorder(root))}`);Preorder processes the node, then the left subtree, then the right. Postorder processes the left subtree, then the right, then the node. Inorder sits between them: left, node, right.
Preorder alone does not fix the tree shape. Pair it with the inorder sequence, rebuild the tree, then run postorder. If the preorder lists null markers for missing children, it is enough on its own.
No. Inorder is sorted only when the tree is a binary search tree. The tree with root 5, left child 9 and right child 1 gives [9, 5, 1].
Preorder finishes a whole subtree before moving on, giving [A, B, D, E, C] on the example. Level order visits every node at one depth first, giving [A, B, C, D, E].
No. Recursion uses the call stack to remember pending work. An iterative version keeps an explicit stack instead. Both use O(h) extra space.