Tree traversals

Why it matters

Almost every tree problem walks the tree in one of a few fixed orders. Choosing the right order is often half the solution. A function that copies a tree must create a parent before its children, while a function that deletes a tree must delete the children first. Interviewers ask for these orders in two forms: the short recursive version, and the iterative version that uses a stack you manage yourself. This lesson teaches both, so you can explain each one on a whiteboard and write it in code.

Level order, the fourth traversal, uses a queue instead of recursion. It gets its own lesson, because it needs a different way of thinking about levels.

The idea

A traversal is a way to visit every node of a tree exactly once. The word "visit" means doing some work at the node, such as printing its value, adding it to a list or comparing it with something. The traversal decides the order in which the visits happen.

Start with a simple family picture. Suppose you walk into a house with three rooms, and each room has its own rooms inside. You have three moments to act for any room: when you first step in, after you finish the left part, and when you leave for the last time. Each of the three depth-first orders picks one of those moments.

A depth-first traversal goes as deep as it can before it backtracks. It always finishes the whole left subtree before it starts the right one. The three depth-first orders differ only in when the node itself is visited relative to its two subtrees:

The word "pre" means the node comes before its children. "In" means the node sits between the left and right subtrees. "Post" means the node comes after its children. Those three words are the whole rule, so say them out loud if you find yourself mixing them up.

Here is the tree we will use for the whole lesson. It is the same tree as before, with the level-order input 1 2 3 4 5 -1 6:

        1
       / \
      2   3
     / \   \
    4   5   6

The three depth-first orders on this tree are:

• preorder: 1, 2, 4, 5, 3, 6
• inorder: 4, 2, 5, 1, 3, 6
• postorder: 4, 5, 2, 6, 3, 1

Three rows of the same six nodes, one row per depth-first order, with the node in its visit position highlighted

You can check each one by applying the rule to each node. For preorder, the root 1 comes first. Then the whole left subtree of 1, which is 2 with children 4 and 5, gives 2, 4, 5. Then the right subtree of 1, which is 3 with the right child 6, gives 3, 6. So the full list is 1, then 2, 4, 5, then 3, 6. Try the inorder and postorder yourself before reading on. If you get them right, the rule is clear.

Level order is different

Level order visits the nodes one level at a time, from the top, and from left to right inside each level. For this tree it gives 1, 2, 3, 4, 5, 6. It is not depth-first, because it moves across the tree, not down. We cover it in the next lesson.

The recursive version

Each depth-first traversal is a short recursive function. The base case is a null node, which does nothing. The recursive case makes two calls, one for each child, and performs the visit before, between or after those calls.

void preorder(TreeNode* n) {
    if (!n) return;
    cout << n->val << " ";      // visit before the children
    preorder(n->left);
    preorder(n->right);
}
 
void inorder(TreeNode* n) {
    if (!n) return;
    inorder(n->left);
    cout << n->val << " ";      // visit between the children
    inorder(n->right);
}
 
void postorder(TreeNode* n) {
    if (!n) return;
    postorder(n->left);
    postorder(n->right);
    cout << n->val << " ";      // visit after the children
}

Look at the three functions side by side. They are identical except for one line, the line with the cout. Moving that line changes the order and nothing else. This is why the bug "I put the print in the wrong place" is so common. The code still runs, and the output looks like a list of numbers, but the order is wrong.

Most of the examples in this lesson do not print directly. They collect the values in a vector, so that you can test the result and print it in one place. The next program does that and prints the three orders for the input in the box.

Type this into the Input box, on one line, and then click Run:

1 2 3 4 5 -1 6

preorder: 1 2 4 5 3 6
inorder: 4 2 5 1 3 6
postorder: 4 5 2 6 3 1

Compare the output with the list you wrote earlier. It should match. Notice that every order contains the same six numbers. Only the sequence changes. That is the first property of a traversal: it visits every node exactly once, so the three lists are permutations of each other.

Tracing the preorder call by call

Tracing is the best way to make the recursion concrete. The table shows each call to preorder, what it does, and the output after it finishes. A call with a null argument returns at once, so those rows are short.

The last row ends the traversal. Every call has either visited a node or returned from a null child. Each real node is visited once, and each null child costs one call that does nothing. In total the function makes about 2n calls, where n is the number of real nodes, because each node has two child slots and each slot makes one call.

What happens inside

Each recursive call takes a frame on the call stack. A frame holds the argument (the node pointer) and the place in the function to return to. Picture a stack of plates. A new call puts a plate on top, and a return takes the top plate off.

When preorder(1) makes its first call, the stack holds two frames, one for 1 and one for 2. When preorder(4) returns, its frame is removed, and the stack holds the frames for 1 and 2 again, now waiting at their second call. The stack depth at any moment is the number of nodes on the path from the root to the node you are at. This is why the stack depth equals the height of the tree, plus one for the call on the root.

Worked example: the iterative inorder

Recursion is short, but the computer uses the call stack for it. You can write the same traversal with your own stack. The idea for inorder goes like this: walk as far left as you can, pushing each node you pass. When you cannot go further left, pop the most recent node, visit it, and then move to its right child. Then repeat.

The visualizer below uses a stack to show the push and pop steps. Step through it while you read the code.

Here is the program. Its input is the same tree.

4 2 5 1 3 6

Trace the first steps. The stack starts empty, and cur is the root, 1. The inner loop pushes 1, then moves to its left child 2, pushes 2, then moves to 4, pushes 4, and then cur becomes null. The stack now holds 1, 2, 4 with 4 on top.

The outer step pops 4 and visits it. Output: 4. Then cur becomes 4's right child, which is null. The loop checks again. cur is null, but the stack is not empty, so the code pops the top, which is 2, and visits it. Output: 4 2. Then cur moves to 2's right child, 5. The inner loop pushes 5, and 5 has no left child. The stack now holds 1 and 5. Pop 5, visit it. Output: 4 2 5. Then cur is null, so pop 1, visit it, and output 4 2 5 1. Then cur moves to 1's right child, 3. The inner loop pushes 3, and 3 has no left child, so pop 3, visit it, then move to its right child 6. Push 6, pop 6, visit it. The stack is empty and cur is null, so the loop stops with 4 2 5 1 3 6.

Notice the pattern. A node is visited only when it is popped, and it is popped only after its whole left side has been finished. That is exactly the inorder rule, left, node, right, written as a loop.

Iterative preorder

Preorder is simpler, because a node is visited the moment it is seen. Push the root. Then, while the stack is not empty, pop a node, visit it, and push its children. Push the right child first and the left child second. A stack gives last-in, first-out order, so the left child is popped first, and the whole left side is finished before the right side starts.

1 2 4 5 3 6

Trace it. The stack holds 1. Pop 1 and visit it. Push its right child 3, then its left child 2. The stack now has 3 at the bottom and 2 on top. Pop 2 and visit it. Push 5, then 4. Pop 4 and visit it. Nothing to push. Pop 5 and visit it. Pop 3 and visit it, and push its right child 6. Pop 6. The output is 1 2 4 5 3 6, which matches the recursive preorder.

Iterative postorder with a reversal trick

Postorder is the hardest of the three to do without recursion, because the node must wait until both children are finished. There is a neat trick. If you visit the nodes in the order node, right, left, which is a mirror image of preorder, the list comes out in the reverse of postorder. So you collect the values in that order and then reverse the list.

Check the idea on the example tree. The mirror order gives 1, 3, 6, 2, 5, 4. Reverse it and you get 4, 5, 2, 6, 3, 1, which is the postorder list. The trick works for any binary tree, because the reverse of "node, right, left" is always "left, right, node".

4 5 2 6 3 1

This version uses O(n) extra memory for the output list, which the recursive version also needs for its vector. The stack itself holds at most about h nodes for this tree shape, because each pop replaces one node with its children.

Leaves in left-to-right order

A common question asks for the leaves, in order from left to right. The preorder-style recursion does this directly: when a node has no children, it is a leaf, so you add it. The order of the calls is already left to right, so the leaves come out in the right order without any extra work.

Here is the code as a function. You will turn it into a complete program in the practice section. The output for the example tree is 4 5 6.

void leaves(TreeNode* n, vector<int>& out) {
    if (!n) return;
    if (!n->left && !n->right) {
        out.push_back(n->val);
        return;
    }
    leaves(n->left, out);
    leaves(n->right, out);
}

Visualizing a whole traversal

The visualizer below runs a full traversal on a binary search tree. It builds the tree from the numbers in its box (8, 3, 10, 1, 6, 14 and 4 by default) and lets you choose the order from the Order menu. A binary search tree keeps smaller numbers on the left and bigger ones on the right, so the inorder order gives the numbers in sorted order. That is a property of search trees, not of every binary tree. For this lesson, watch the order in which nodes light up. The rule you have learned, node before, between or after the children, decides that order for any tree.

Choose preorder, then inorder, then postorder, and compare the three runs on the same tree. Watch where the node is highlighted relative to its children in each run. The visualizer is a search tree, so the numbers look different from the picture in this lesson, but the sequence of steps follows the same three rules.

Complexity

Let n be the number of nodes and h the height. For each depth-first order, both the recursive and the iterative versions do the following.

• Time: O(n). Every node is visited once, and every null child costs one constant step. The total is proportional to n.
• Space for the recursion: O(h). The call stack holds one frame for each level from the root down to the current node, so its depth is at most the height plus one.
• Space for the iterative version: O(h). The stack holds the nodes on the current path, plus the siblings waiting for their turn. The size is also bounded by the height.
• Space for the output: O(n). Any list that holds all the values needs room for n values.

The skewed case is the worst for stack space. A tree that is a single chain of n nodes has a height of n, so the recursion goes n calls deep. A large skewed tree can overflow the default call stack, which is typically a few megabytes, and the program then crashes. The iterative version uses the heap for its stack, so it does not hit that limit in the same way, although the stack still holds about n nodes in the skewed case.

A worked example on skewed trees

A skewed tree is a useful test, because each order is easy to trace by hand. Take the list 1 2 -1 3 -1 4. Read it in level order. The root 1 has a left child 2 and no right child. Node 2 has a left child 3 and no right child. Node 3 has a left child 4. So the tree is a chain that leans to the left:

    1
   /
  2
 /
3
/
4

Trace inorder on this chain. The call inorder(1) makes the call inorder(2), which makes inorder(3), which makes inorder(4). The node 4 has two null children, so the call on 4 visits 4 and returns. Back in the call on 3, the work is done: it has visited its left side, which is 4, and now it visits 3. Back in the call on 2, the same happens, so it visits 2. Finally, the call on 1 visits 1. The output is 4 3 2 1.

Now do the other two orders on the same chain. Preorder visits 1 first, then 2, then 3, then 4, so it gives 1 2 3 4. Postorder visits the deepest node first and the root last, so it gives 4 3 2 1. Inorder and postorder agree here, and that is not a coincidence. In a tree with no right children, the "between" visit and the "after" visit happen at the same moment, because the right subtree is always empty.

Now flip the chain so that every node has only a right child: the list 1 -1 2 -1 3 -1 4. Here the left subtrees are all empty. Preorder and inorder agree, and both give 1 2 3 4, while postorder gives 4 3 2 1. The rule is the same in both cases. When one side of every node is empty, the orders that differ only on that side collapse into one.

A quick table of the three orders for both chains:

Run the first program in this lesson again, with the Input box set to 1 2 -1 3 -1 4. The three lines it prints are preorder: 1 2 3 4, inorder: 4 3 2 1 and postorder: 4 3 2 1, which matches the first row of the table.

The skewed case is also where the cost of recursion shows. A chain of n nodes makes n nested calls, so the call stack grows to n frames. A balanced tree of the same size needs only about log n frames. That is why the stack-depth point in the complexity section matters in practice, not only in theory.

Choosing the order

When you face a new tree problem, ask one question about the answer you need: does the answer at a node depend on its children, or on its parent? Your answer chooses the order.

• If the node needs its children's answers first, use postorder. Examples are the size of a subtree, its height, its sum, and deleting a tree. The children must finish before the node can be decided.
• If the node needs information from its ancestors, use preorder, and pass the information down as a parameter. Examples are the depth of each node, the running sum of the path from the root, and printing an outline with indentation.
• If the answer must come out in sorted order from a binary search tree, use inorder. The left side holds the smaller values, so the sequence rises.
• If the answer depends on the level of each node, use level order, which is the next lesson.

Here is the outline printer, which is preorder with a depth parameter. Each node prints before its children, indented by its depth:

void outline(TreeNode* n, int depth) {
    if (!n) return;
    cout << string(depth * 2, ' ') << n->val << "\n";
    outline(n->left, depth + 1);
    outline(n->right, depth + 1);
}

Call it as outline(root, 0). The depth is passed down, so each child knows its own depth without asking its parent. That is the signature of a preorder problem.

What happens inside the iterative inorder

The iterative inorder keeps its own stack of nodes that are waiting. It helps to say exactly what the stack holds at each moment. When the inner loop walks left, it pushes every node it passes, and those nodes are the ancestors of the current position whose visit is still waiting. The top of the stack is the nearest of them.

For the example tree from the start of the lesson, the first inner loop pushes 1, then 2, then 4. At that moment the stack holds 1 at the bottom, then 2, then 4 on top. None of them has been visited yet. The loop then pops 4, visits it, and moves to 4's right child, which is null. The stack now holds 1 and 2, and the next pop gives 2. This is why the output begins 4 2. Each node waits on the stack until its left side is finished, and then it is popped and visited.

The stack never holds more than about h nodes, where h is the height, because it only holds the path from the root to the current position. The stack lives on the heap, which is much larger than the call stack, so the iterative version does not overflow on a long chain the way a deep recursion can. It still uses memory proportional to the height in the worst case.

Edge cases

Test each order on these inputs before you trust it.

• The empty tree. The iterative inorder starts with cur set to null and an empty stack, so its loop never runs and it returns an empty vector. The iterative preorder and postorder return early with if (!root) return out;. The recursive versions return at their first line. None of them crash, and all print nothing.
• One node. Every order returns that single value, because the node has no children.
• A long chain. The recursive versions go n calls deep, which is the risk described above. The iterative versions use the heap for the stack and handle long chains better.
• Duplicate values. Traversals visit each node once, so a repeated value appears as many times as it occurs in the tree. The orders still hold, but a search by value may find the wrong copy first.

Stopping early

Sometimes you need only the first node that matches, not the whole list. A recursive search can return as soon as it finds one, and the rest of the tree is never visited. The || operator helps, because it stops at the first true result, so the right subtree is searched only when the left one fails:

bool containsPreorder(TreeNode* n, int target) {
    if (!n) return false;
    if (n->val == target) return true;
    return containsPreorder(n->left, target) || containsPreorder(n->right, target);
}

The search runs in O(n) in the worst case, when the value is missing or near the end. It runs in less time when the value appears early in preorder. This early exit is a common pattern, and it works with any of the three orders.

Morris traversal, a preview

The iterative inorder uses O(h) space for its stack. There is a method called the Morris traversal that does inorder with O(1) extra space. It works by temporarily linking each node's inorder predecessor back to the node, so that the walk can return without a stack. When the walk is done, it removes those links. The idea is advanced, and you do not need it for this module. Know that it exists, and that it changes the tree while it runs, so the links must be removed before the function returns.

Common mistakes and their real messages

Printing in the wrong place

If you print inside the wrong call, the order changes but the program still runs. For example, printing the node before the left call in a function meant for inorder gives preorder. The fix is to compare the output with a small tree by hand. Use the three-node tree 1 2 3, which has 1 with children 2 and 3. Its inorder is 2 1 3. If your code prints 1 2 3, it is preorder.

Forgetting to include the stack header

The iterative versions need #include <stack>. If you leave it out, the compiler reports this message:

error: 'stack' is not a member of 'std'

The same kind of message appears for queue and vector. The fix is always to add the matching #include line at the top of the file.

Forgetting to move right in the iterative inorder

The most dangerous mistake is leaving out the last line of the inner loop, cur = cur->right;. The loop keeps running with cur pointing at the same node, or a null node, and the stack never empties in the right way. In a program like the one above, that produces an infinite loop, and the program never ends. Always check that the loop variable changes on every pass.

Calling top() on an empty stack

The code st.top() reads the top element. If the stack is empty, that read is undefined behaviour. In the iterative inorder loop, the check while (cur || !st.empty()) guards the call, so the stack is not empty when top() runs. If you change that check to while (cur), the loop stops too early and misses nodes. If you change it to something that can reach top() with an empty stack, the program may crash with exit status 139.

Mixing the orders in one function

It is tempting to write one function that does all three orders. That is fine as a teaching exercise, but in an interview the answer should name one order and explain why it fits the problem. Say "I need the parent before the children, so this is preorder" and the interviewer sees that you understand the idea.

Debugging walkthrough

Suppose you wrote a traversal and the output is 4 2 1 5 3 6 for the example tree. That order is not one of the three, so something is wrong. Follow these steps.

First, write the expected inorder on paper for this tree. It is 4 2 5 1 3 6. Then compare it, position by position, with your output. The first difference is at index 2: you printed 1, but inorder wants 5. The number 1 came out too early, which means the visit happened before the left subtree of 1 was finished.

Second, look at the function for the line that visits the node. Ask whether that line sits between the two recursive calls. In the broken version, the line out.push_back(n->val); sits before inorder(n->left, out);, so it runs first. Moving it back between the calls fixes the order.

Third, test the smallest tree that shows the problem. The tree 1 2 3 is enough to show whether inorder is right: the answer must be 2 1 3. A tree with a left child only, such as 1 2, tests the left recursion alone.

Fourth, run the iterative version on the same input and compare the two. If the recursive version is right and the iterative one is wrong, the bug is in the stack logic. If both are wrong in the same way, the bug is in the order you think is right, so check your rule again.

Interview questions you should be ready for

• Which traversal gives the sorted order of a binary search tree? Inorder, because it visits the left subtree (smaller values), then the node, then the right subtree (bigger values).
• Why does postorder suit deleting a tree? You must free the children before the parent, because the parent holds the only pointers to them. If you free the parent first, you lose the way to reach its children.
• How do you write inorder without recursion? Use a stack. Walk left as far as you can, pushing nodes. Pop, visit, and move right. Repeat until the stack is empty and there is no current node.
• What is the space cost of a recursive traversal? O(h), the height, because of the call stack. It is O(n) in the worst case of a skewed tree.
• Can one traversal recover the tree? Not alone. Preorder and inorder together identify a binary tree when the values are distinct. Preorder alone does not, because a node with one child could hold it on the left or on the right.

Real-world uses

Copying a folder is a preorder job. You create the folder first, then copy each child inside it, so the parent exists before its contents. Deleting a folder is a postorder job. You delete the files and subfolders first, and then the folder is empty and can be removed. A calculator that works with an expression tree uses postorder for evaluation. For (2 + 3) * 4, the tree has * at the root, + on the left with children 2 and 3, and 4 on the right. Postorder gives 2, 3, +, 4, *. That list is the same expression in reverse Polish notation, and a stack can evaluate it from left to right: push 2, push 3, apply + to the top two values to get 5, push 4, apply * to get 20.

Practice

1. Write the preorder, inorder and postorder of the tree with input 1 -1 2 -1 3 by hand. Then run the three functions on it to check.

2. Write the inorder traversal of the tree with input 1 2 -1 3. Predict the output before you run it.

3. Write a recursive function int countNodes(TreeNode* n) that uses postorder, meaning it computes the answer from the children and then adds the current node.

int countNodes(TreeNode* n) {
    if (!n) return 0;
    int left = countNodes(n->left);     // children first
    int right = countNodes(n->right);
    return left + right + 1;            // then the node itself
}

4. Write void leaves(TreeNode* n, vector<int>& out) (shown in this lesson) as a complete program that reads the input and prints the leaves on one line. For the example input, the output is 4 5 6.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
 
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front();
        q.pop();
        if (i < a.size() && a[i] != -1) {
            n->left = new TreeNode(a[i]);
            q.push(n->left);
        }
        i++;
        if (i < a.size() && a[i] != -1) {
            n->right = new TreeNode(a[i]);
            q.push(n->right);
        }
        i++;
    }
    return root;
}
 
void printLine(const vector<int>& v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i) cout << " ";
        cout << v[i];
    }
    cout << "\n";
}
 
void leaves(TreeNode* n, vector<int>& out) {
    if (!n) return;
    if (!n->left && !n->right) {
        out.push_back(n->val);
        return;
    }
    leaves(n->left, out);
    leaves(n->right, out);
}
 
int main() {
    vector<int> values;
    int x;
    while (cin >> x) values.push_back(x);
    vector<int> out;
    leaves(build(values), out);
    printLine(out);
    return 0;
}

5. Write iterative postorder with two stacks, instead of the reversal trick. Hint: the first stack produces the node, left, right order; push each popped node onto a second stack, and pop the second stack to get the answer.

vector<int> postorderTwoStacks(TreeNode* root) {
    vector<int> out;
    if (!root) return out;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* n = s1.top();
        s1.pop();
        s2.push(n);
        if (n->left) s1.push(n->left);
        if (n->right) s1.push(n->right);
    }
    while (!s2.empty()) {
        out.push_back(s2.top()->val);
        s2.pop();
    }
    return out;
}

6. Explain in your own words why the inorder traversal of a binary search tree gives sorted output.

7. Write void mirror(TreeNode* n) that swaps the left and right child of every node. Use any traversal, and say which one you chose and why.

void mirror(TreeNode* n) {
    if (!n) return;
    swap(n->left, n->right);   // swap before or after the children; both work
    mirror(n->left);
    mirror(n->right);
}

8. Draw the expression tree for (4 - 1) * (2 + 3) and write its postorder. The postorder is the reverse Polish form of the expression.

9. Explain why postorder is the right order for freeing every node of a tree. What goes wrong if you free the root first?

10. Write a function that returns the number of times each order would call the function on a null child, for a tree with n nodes. Show that every order makes the same number of calls.

What you now know

• A traversal visits every node once. The three depth-first orders are preorder (node first), inorder (node between the children) and postorder (node last).
• Each depth-first order is a short recursive function. Moving the visit line is the only change between them.
• Preorder copies and saves trees. Inorder gives sorted output for search trees. Postorder deletes trees and evaluates expressions.
• The iterative versions use a stack you manage. Inorder pops and then goes right. Preorder pushes right before left. Postorder is the reverse of node, right, left.
• Every traversal runs in O(n) time, and uses O(h) space for the recursion or the stack.
• The common bugs are a visit in the wrong place, a missing #include, and a missing cur = cur->right in the iterative inorder loop, which causes an infinite loop.