Why this matters
A traversal visits every node of a tree once, in a fixed order. Many tree programs need one. Printing a file tree, adding up the values in a tree and checking a tree for a value all start with a traversal.
The usual way to write a traversal is recursion, where a function calls itself on the left child and the right child. Recursion is short and easy to read. But each call uses memory on the call stack, which is a fixed block of memory the program gets for function calls. A tree that is 100,000 nodes deep, such as a long chain of nodes that only goes left, can use up that block. The program then crashes with a stack overflow.
This lesson writes the same traversals with a loop and a std::stack, which is a container from the C++ standard library that holds items in last-in, first-out order. You manage the stack yourself, and its size is limited only by the heap. The previous lessons in this module covered tree vocabulary and the basic recursive traversals. This lesson does not repeat them. The next lesson handles postorder, the order that visits children before their parent, which needs one extra variable.
The idea: a stack holds the nodes you still need to visit
Start with a plain picture. You are reading a book with a pile of bookmarks. Each time you open a chapter that has a sub-chapter inside it, you put a bookmark on the chapter you are leaving, so you can come back to it later. When you finish a sub-chapter, you take the top bookmark off the pile and go back to where it points.
A stack works the same way. Its rules are:
push(x)putsxon the top.pop()removes the top item. The top item is the one pushed most recently.top()reads the top item without removing it.
In C++ you write std::stack<const Node*> st;, then st.push(p), st.top() and st.pop(). Two details matter. First, pop() returns nothing, so you read the item with top() first and then call pop(). Second, top() on an empty stack is an error, so you check st.empty() before you read the top.
The lesson uses this tree for every example:
4
/ \
2 6
/ \ / \
1 3 5 7Node 4 is the root. Its left child is 2 and its right child is 6. The leaves are 1, 3, 5 and 7.
We use const Node* in the stack. A pointer is a value that stores where another value lives in memory. Here, each stack entry says "the node at this address". The tree owns the nodes. The stack only borrows them to visit, so it never deletes them.
Preorder: visit the node, then its left side, then its right side
Preorder means the node is visited before any of its children. For the tree above, preorder is 4 2 1 3 6 5 7. The root comes first, then the whole left subtree (2, 1, 3), then the whole right subtree (6, 5, 7).
The recursive version is short:
void preorder_recursive(const Node* node) {
if (node == nullptr) return;
visit(node);
preorder_recursive(node->left.get());
preorder_recursive(node->right.get());
}To write it with a stack, use this rule. Pop one node from the stack. Visit it. Then push its children, so that they are popped later. The left child must be popped first, so the left child goes on the stack last. That means you push the right child first and the left child second.
Walk through the example with this rule.
- Push the root, 4. The stack is
[4]. - Pop 4 and visit it. Output so far:
4. Push right child 6, then left child 2. The stack is[6, 2], with 2 on top. - Pop 2 and visit it. Output:
4 2. Push right child 3, then left child 1. The stack is[6, 3, 1], with 1 on top. - Pop 1 and visit it. Output:
4 2 1. Node 1 has no children. The stack is[6, 3]. - Pop 3 and visit it. Output:
4 2 1 3. Node 3 has no children. The stack is[6]. - Pop 6 and visit it. Output:
4 2 1 3 6. Push right child 7, then left child 5. The stack is[7, 5], with 5 on top. - Pop 5 and visit it. Output:
4 2 1 3 6 5. The stack is[7]. - Pop 7 and visit it. Output:
4 2 1 3 6 5 7. The stack is empty, so the loop stops.
Here is the code:
#include <memory>
#include <stack>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
std::vector<int> preorder(const Node* root) {
std::vector<int> out;
std::stack<const Node*> todo;
if (root != nullptr) {
todo.push(root);
}
while (!todo.empty()) {
const Node* cur = todo.top();
todo.pop();
out.push_back(cur->value);
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return out;
}The if (cur->right) line tests whether the unique_ptr holds a node. A unique_ptr converts to true when it is not empty. The .get() call returns the raw pointer that the stack stores.
Inorder: left side, then the node, then the right side
Inorder visits the left subtree first, then the node itself, then the right subtree. For the example tree, inorder is 1 2 3 4 5 6 7. This order matters for search trees in a later module, because for a search tree it gives the values in sorted order.
The stack version of inorder needs a different rule from preorder. You cannot visit a node when you first see it, because its left subtree comes first. So you do two things in a loop:
- Walk left as far as you can. Each node you pass goes on the stack, because you will come back to it.
- When you cannot go left, pop a node from the stack. Visit it. Then move to its right child, and start step 1 again from there.
The walk left is an inner loop. Its job is to push a whole chain of left nodes. The outer loop continues while there is a node to walk from, or while the stack still holds nodes that have not been visited.
Trace on a small tree
Start with a three-node tree, so that every push and pop fits on the screen:
2
/ \
1 3The code below has the same logic as the real version, with a print statement added to each push and pop. Save it as a file and compile it. Its output is shown after the code.
#include <iostream>
#include <memory>
#include <stack>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
using NodePtr = std::unique_ptr<Node>;
NodePtr make(int value, NodePtr left = nullptr, NodePtr right = nullptr) {
return std::make_unique<Node>(Node{value, std::move(left), std::move(right)});
}
std::vector<int> inorder_traced(const Node* root) {
std::vector<int> out;
std::stack<const Node*> st;
const Node* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
std::cout << "push " << cur->value << " stack size " << st.size() << '\n';
cur = cur->left.get();
}
cur = st.top();
st.pop();
std::cout << "pop " << cur->value << " visit " << cur->value << " stack size " << st.size() << '\n';
out.push_back(cur->value);
cur = cur->right.get();
}
return out;
}
int main() {
auto small = make(2, make(1), make(3));
for (int x : inorder_traced(small.get())) std::cout << x << ' ';
std::cout << '\n';
}Compile with g++ -std=c++20 -Wall -o trace inorder_traced.cpp and run ./trace. The output is:
push 2 stack size 1
push 1 stack size 2
pop 1 visit 1 stack size 1
pop 2 visit 2 stack size 0
push 3 stack size 1
pop 3 visit 3 stack size 0
1 2 3 Read the output line by line, and match each line to the rules.
- The walk left starts at 2 and pushes it. Then it moves to 2's left child, 1, and pushes that too. Node 1 has no left child, so the walk stops. The stack holds
2, 1, with 1 on top. - The stack is not empty, so pop. The top is 1. Visit 1. The stack now holds only 2. Node 1 has no right child, so the current node is empty and the next loop starts from the top of the stack.
- Pop 2 and visit it. The stack is now empty. Move to 2's right child, 3.
- Walk left from 3. Node 3 has no left child, so push 3 and stop. Pop 3 and visit it. Node 3 has no right child. The current node is empty and the stack is empty, so the loop ends.
The full inorder function
std::vector<int> inorder(const Node* root) {
std::vector<int> out;
std::stack<const Node*> st;
const Node* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left.get();
}
cur = st.top();
st.pop();
out.push_back(cur->value);
cur = cur->right.get();
}
return out;
}Run the full 7-node tree from the top of this lesson through both functions. The complete program is below. Both functions are shown in one file, so you can compile it and check the results yourself.
#include <iostream>
#include <memory>
#include <stack>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
using NodePtr = std::unique_ptr<Node>;
NodePtr make(int value, NodePtr left = nullptr, NodePtr right = nullptr) {
return std::make_unique<Node>(Node{value, std::move(left), std::move(right)});
}
std::vector<int> preorder(const Node* root) {
std::vector<int> out;
std::stack<const Node*> todo;
if (root != nullptr) {
todo.push(root);
}
while (!todo.empty()) {
const Node* cur = todo.top();
todo.pop();
out.push_back(cur->value);
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return out;
}
std::vector<int> inorder(const Node* root) {
std::vector<int> out;
std::stack<const Node*> st;
const Node* cur = root;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left.get();
}
cur = st.top();
st.pop();
out.push_back(cur->value);
cur = cur->right.get();
}
return out;
}
void print(const std::vector<int>& v) {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
auto root = make(4,
make(2, make(1), make(3)),
make(6, make(5), make(7)));
std::cout << "preorder: ";
print(preorder(root.get()));
std::cout << "inorder: ";
print(inorder(root.get()));
}Compile it with g++ -std=c++20 -Wall -o traversals traversals.cpp and run it. The output is:
preorder: 4 2 1 3 6 5 7
inorder: 1 2 3 4 5 6 7 The trailing space after each line comes from print, which writes a space after every number. That is harmless here.
A third example: stop early and measure the stack
The first two examples visited every node. Two useful variations stop early, or report how much memory the stack used.
The first variation is a search for the kth smallest value. For the example tree, the 1st smallest is 1, the 2nd is 2, and so on. Inorder gives values in that order, so the program counts values as they are visited and returns as soon as the count reaches k. It never visits the rest of the tree. Use the same Node type as before.
int kth_smallest(const Node* root, int k) {
std::stack<const Node*> st;
const Node* cur = root;
int seen = 0;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left.get();
}
cur = st.top();
st.pop();
++seen;
if (seen == k) return cur->value;
cur = cur->right.get();
}
return -1;
}The second variation records the largest size the stack reached. This is useful when you want to know how much memory a traversal needs. A tree that is shaped like a chain (every node has one child) fills the stack very differently from a full tree.
std::vector<int> preorder_with_peak(const Node* root, std::size_t& peak) {
std::vector<int> out;
std::stack<const Node*> todo;
peak = 0;
if (root != nullptr) todo.push(root);
while (!todo.empty()) {
if (todo.size() > peak) peak = todo.size();
const Node* cur = todo.top();
todo.pop();
out.push_back(cur->value);
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return out;
}The program below runs both on the example tree and on a chain 5 -> 4 -> 3 -> 2 -> 1, where each node has only a left child. Its output is shown after the code.
#include <iostream>
#include <memory>
#include <stack>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
using NodePtr = std::unique_ptr<Node>;
NodePtr make(int value, NodePtr left = nullptr, NodePtr right = nullptr) {
return std::make_unique<Node>(Node{value, std::move(left), std::move(right)});
}
std::vector<int> preorder_with_peak(const Node* root, std::size_t& peak) {
std::vector<int> out;
std::stack<const Node*> todo;
peak = 0;
if (root != nullptr) todo.push(root);
while (!todo.empty()) {
if (todo.size() > peak) peak = todo.size();
const Node* cur = todo.top();
todo.pop();
out.push_back(cur->value);
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return out;
}
int kth_smallest(const Node* root, int k) {
std::stack<const Node*> st;
const Node* cur = root;
int seen = 0;
while (cur != nullptr || !st.empty()) {
while (cur != nullptr) {
st.push(cur);
cur = cur->left.get();
}
cur = st.top();
st.pop();
++seen;
if (seen == k) return cur->value;
cur = cur->right.get();
}
return -1;
}
int main() {
auto root = make(4,
make(2, make(1), make(3)),
make(6, make(5), make(7)));
std::size_t peak = 0;
auto order = preorder_with_peak(root.get(), peak);
std::cout << "preorder:";
for (int x : order) std::cout << ' ' << x;
std::cout << "\npeak stack size: " << peak << '\n';
auto chain = make(5, make(4, make(3, make(2, make(1)))));
auto chain_order = preorder_with_peak(chain.get(), peak);
std::cout << "chain preorder:";
for (int x : chain_order) std::cout << ' ' << x;
std::cout << "\nchain peak stack size: " << peak << '\n';
for (int k = 1; k <= 8; k += 3) {
std::cout << "kth_smallest(" << k << ") = " << kth_smallest(root.get(), k) << '\n';
}
}Output:
preorder: 4 2 1 3 6 5 7
peak stack size: 3
chain preorder: 5 4 3 2 1
chain peak stack size: 1
kth_smallest(1) = 1
kth_smallest(4) = 4
kth_smallest(7) = 7Two results need explanation. The full tree peaks at 3, when the stack holds 6, 3 and 1: two right children waiting their turn, and the left child that was just pushed. The chain peaks at 1. Each node has only a left child, so the stack never holds more than one node at a time. The chain has five levels, but the stack stays small, because the left child is pushed, then immediately popped.
Recursion does not behave this way. In recursion, each level of the chain adds a new call to the call stack, so a chain of 100,000 nodes makes 100,000 calls. The explicit stack here stores only the nodes that still need work, so the memory used depends on the shape of the tree.
Common mistakes
Mistake 1: pushing the left child first in preorder
A preorder program that pushes the left child before the right child produces the children in reverse order. Here is the broken line order in the loop:
if (cur->left) todo.push(cur->left.get());
if (cur->right) todo.push(cur->right.get());Running it on the example tree prints:
4 6 7 5 2 3 1The left subtree is visited after the right one, so the output is not preorder. Remember that a stack is last-in, first-out. The item pushed last is popped first. To visit the left child first, push it last.
Mistake 2: forgetting to move to the right child in inorder
In inorder, the last step inside the outer loop must set cur to the right child. If you leave that line out, cur still points at the node you just visited. The outer loop then runs the inner loop on that same node again. It pushes the node, moves to its left child, and repeats until the left chain runs out. Since nothing ever moves cur forward, the loop never ends.
You can see this with the broken version, which we ran with timeout 3. The program printed nothing and was stopped after 3 seconds, with exit code 124. Exit code 124 is what the timeout command returns when it has to stop a program. The program does not crash. It pushes and pops the same node forever, and the output vector keeps growing with copies of the value 1. Each time through the loop should move cur closer to the end of the tree, and you should check that it does.
Mistake 3: popping an empty stack
top() and pop() on an empty std::stack are undefined behaviour. This means the C++ standard does not say what happens, so the program may crash, print garbage, or seem to work. The standard library in g++ can check for this if you compile with -D_GLIBCXX_ASSERTIONS. This small program pops one more time than it pushes:
#include <iostream>
#include <stack>
void pop_too_many() {
std::stack<int> s;
s.push(1);
s.pop();
std::cout << "top of empty stack: " << s.top() << '\n';
}
int main() {
pop_too_many();
}Save it as pop_too_many.cpp, compile with g++ -std=c++20 -Wall -g -D_GLIBCXX_ASSERTIONS -o pop_too_many pop_too_many.cpp, and run it. The real message is:
/usr/include/c++/15/bits/stl_stack.h:260: std::stack<_Tp, _Sequence>::reference std::stack<_Tp, _Sequence>::top() [with _Tp = int; _Sequence = std::deque<int, std::allocator<int> >; reference = int&]: Assertion '!this->empty()' failed.The fix is to test !st.empty() before every top() or pop(). The traversals in this lesson do that in their loop conditions. Without -D_GLIBCXX_ASSERTIONS, the same mistake usually runs without any message, which makes it harder to find.
Mistake 4: using the return value of pop
pop() removes the top item and returns nothing. People coming from other languages often expect it to return the item. In C++ this is a compile error:
#include <stack>
int main() {
std::stack<int> s;
s.push(4);
auto x = s.pop();
return x;
}Compiling with g++ -std=c++20 -Wall -c -o /dev/null bad_pop.cpp gives:
bad_pop.cpp: In function ‘int main()’:
bad_pop.cpp:6:10: error: deduced type ‘void’ for ‘x’ is incomplete
6 | auto x = s.pop();
| ^Read the value with top() first, then call pop(), as the traversal code does.
Mistake 5: forgetting to check for null children
A null pointer means "there is no child here". If you push a null pointer onto the stack and then read cur->value, the program reads memory that is not a node, and it usually crashes. The traversals check each child before pushing it, for example if (cur->right) todo.push(cur->right.get());. Keep that check. The only exception is the root, which the code checks once before the loop starts.
Practice
Exercise 1: trace the stack
Write down the stack contents after each push and pop when you run preorder on this tree:
10
/ \
5 20
\
30Write the stack as a list with the top item last. Then write the final output.
Show the answer
Start with [10]. Pop 10 and visit it. Push right child 20, then left child 5. The stack is [20, 5]. Pop 5 and visit it. It has no children. The stack is [20]. Pop 20 and visit it. Push right child 30. The stack is [30]. Pop 30 and visit it. The stack is empty. The output is 10 5 20 30.
Exercise 2: inorder on a chain
Use inorder on the tree 1 -> 2 -> 3, where each node has only a right child. What is the output, and what is the largest size the stack reaches?
Show the answer
The output is 1 2 3. The inner loop pushes the current node and then stops, because it has no left child. Push 1, then stop. Pop 1, visit it, and move right to 2. Node 2 also has no left child, so push 2 and pop it, visit it, and move to 3. Push 3, pop it, visit it, and the loop ends. The stack holds at most one node at a time, so the largest size is 1.
Exercise 3: find the largest value without recursion
Write a function int max_value(const Node* root) that uses a stack and a preorder walk to find the largest value in a tree. Return -1 for an empty tree, assuming all values are 0 or more.
Show the answer
int max_value(const Node* root) {
if (root == nullptr) return -1;
int best = root->value;
std::stack<const Node*> todo;
todo.push(root);
while (!todo.empty()) {
const Node* cur = todo.top();
todo.pop();
if (cur->value > best) best = cur->value;
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return best;
}On the example tree this returns 7. The order of the walk does not change the answer, because the function looks at every node.
Exercise 4: count the leaves
A leaf is a node with no children. Write int count_leaves(const Node* root) that uses the preorder pattern. On the example tree (4 2 1 3 6 5 7), what should it return?
Show the answer
int count_leaves(const Node* root) {
if (root == nullptr) return 0;
int leaves = 0;
std::stack<const Node*> todo;
todo.push(root);
while (!todo.empty()) {
const Node* cur = todo.top();
todo.pop();
if (!cur->left && !cur->right) ++leaves;
if (cur->right) todo.push(cur->right.get());
if (cur->left) todo.push(cur->left.get());
}
return leaves;
}On the example tree, the leaves are 1, 3, 5 and 7, so the answer is 4.
Exercise 5: predict the output of a broken traversal
A student writes an inorder function where the loop body is:
while (cur != nullptr) {
st.push(cur);
cur = cur->left.get();
}
cur = st.top();
st.pop();
out.push_back(cur->value);What does it return for the example tree, and why?
Show the answer
It never finishes. The walk left pushes 4, 2 and 1. The loop pops 1 and visits it, but cur still points at 1, because nothing moved it to the right child. The next pass of the outer loop pushes 1 again, finds no left child, pops it, and visits it again. The output fills with 1s and the function never returns. The fix is to add cur = cur->right.get(); after out.push_back(...).
Summary
- A traversal visits each node once. An explicit
std::stackreplaces the call stack that recursion uses. - Preorder pops a node, visits it, then pushes the right child and the left child, in that order, so the left child comes out first.
- Inorder walks left and pushes every node it passes. When it cannot go further, it pops a node, visits it, and moves to the right child.
- Always check
!st.empty()beforetop()orpop(), and build with-D_GLIBCXX_ASSERTIONSwhile learning, so the standard library reports the mistake. - The memory a stack traversal uses depends on the shape of the tree. A chain uses little stack space, while a full tree holds more nodes at once.