Return to the blog's main page.
Iterative Tree Traversals: A Practical Guide
Introduction
I don't know how often tree traversals come up in actual software projects, but they are popular in coding interviews and competitive programming.
In this article, I share an approach for implementing tree traversal algorithms iteratively that I found to be simple to remember and implement, while being flexible enough to do anything that a recursive algorithm can (I also didn't like most suggestions I saw online). The main technique is given in section "Iterative Postorder and Inorder Traversal", but first I give some context. I also link to practice problems on leetcode.com for the reader to play with. I provide some solutions, but I suggest trying the problems out first. The code snippets are in C++, but leetcode accepts most languages.
What are Tree Traversals
Mathematically, trees are just connected acyclic graphs. However, in the context of tree traversals, we are usually working with rooted trees represented with a recursive structure such as the following (which is the default definition in Leetcode for binary trees). A leaf is a node with two null pointers as children:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};A tree traversal is an algorithm that visits every node in a tree in a specific order (and does some computation with them, depending on the problem). For binary trees specifically, there are three important orders:
- Preorder: root before children. As we will see, this is the simplest to implement.
- Inorder: left child, then root, then right child. This traversal is most often used on binary search trees (BST). A BST is a rooted binary tree with the additional property that every node in the left subtree has a smaller value than the root, and every node in the right subtree has a larger value than the root. This traversal is called "inorder" because, when used on a BST, it will visit the nodes from smallest to largest.
- Postorder: children before root. It comes up in problems where we have to aggregate information about the entire subtree rooted at each node. Classic examples are computing the size, the height, or the sum of values of the tree.
Because rooted trees are recursive data structures, algorithms on trees are most naturally expressed recursively. Here are the three traversals. I use the function process(node) as a placeholder for whatever computation the problem calls for.
void preorderTraversal(TreeNode* root) {
if (!root) return;
process(root);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
process(root);
inorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (!root) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
process(root);
}Side-note: in C++, pointers are implicitly converted to booleans: a pointer evaluates to true if and only if it is not null. So, in the code above, "if (!root)" is equivalent to "if (root == NULL)".
Traversal problems on leetcode
- https://leetcode.com/problems/binary-tree-preorder-traversal/
- https://leetcode.com/problems/binary-tree-inorder-traversal/
- https://leetcode.com/problems/binary-tree-postorder-traversal/
Why / When to Use an Iterative Traversal
If the recursive implementation is so simple, why bother with an iterative one? Of course, to avoid stack overflow. Most runtime engines/compilers set a limit on how many nested calls a program can make. For example, according to this article:
Default stack size varies between 320k and 1024k depending on the version of Java and the system used. For a 64 bits Java 8 program with minimal stack usage, the maximum number of nested method calls is about 7000.
If the height of the tree is larger than this limit, the program will crash with a stack overflow error. A recursive implementation is safe to use if:
- Somehow we know that the input trees will be small enough.
- The tree is balanced, which means that, for each node, the left and right subtrees have roughly the same height. In a balanced tree, the height is guaranteed to be logarithmic on the number of nodes (indeed, that is why balanced BSTs guarantee O(log n) search time), so any tree that fits in RAM (or even disk) will require a tiny number of recursive calls.
However, if we are not in either of the cases above, an iterative solution is safer.
Recursive and iterative traversals have the same runtime complexity, so this is not a concern when choosing either (all the problems shown in this article can be solved in linear time using either).
The main approach for converting recursive implementations to iterative ones is to "simulate" the call stack with an actual stack where we push and pop the nodes explicitly. This works great "out-of-the-box" with preorder traversal.
Incidentally, when implementing tree traversals we need to make an implementation choice about how to handle NULL pointers. We can be eager and filter them out before adding them to the stack, or we can be lazy and detect them once we extract them from the stack. Both are fine—what matters is to be deliberate and consistent about which approach we are using. I prefer the latter as it yields slightly shorter code, so I will use it in all the following examples. For comparison, here is the iterative preorder traversal with both approaches:
//eager NULL checking
void preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
if (!root) return;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
process(node);
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
}
//lazy NULL checking
void preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
if (!node) continue;
process(node);
stk.push(node->right);
stk.push(node->left);
}
}Note that the right child is pushed to the stack before the left one. This is because we want the left child to be above in the stack so that it is processed first.
Preorder traversal practice problems
- https://leetcode.com/problems/invert-binary-tree/
- https://leetcode.com/problems/maximum-depth-of-binary-tree/
This problem asks to find the depth of a binary tree (follow the link for the description and examples). It requires passing information from each node to its children. We can do this by changing the stack to stack<pair<TreeNode*, int>>, so that we can pass an int to each child, as in the solution below:
int maxDepth(TreeNode* root) {
int res = 0;
stack<pair<TreeNode*, int>> stk;
stk.push({root, 1}); //node, depth
while (!stk.empty()) {
auto node = stk.top().first;
int depth = stk.top().second;
stk.pop();
if (!node) continue;
res = max(res, depth);
stk.push({node->left, depth+1});
stk.push({node->right, depth+1});
}
return res;
}In the code above, the {} notation is used to create pairs (e.g., {root, 0}). If one is not familiar with pairs in C++, or is using a language without the equivalent, a simple alternative is to use two separate stacks, one for the nodes and one for the info.
The next two problems are similar:
- https://leetcode.com/problems/minimum-depth-of-binary-tree/
- https://leetcode.com/problems/path-sum/
- https://leetcode.com/problems/symmetric-tree/
A solution for the last one, this time using a stack with a pair of nodes:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
stack<pair<TreeNode*, TreeNode*>> stk;
stk.push({root->left, root->right});
while (!stk.empty()) {
TreeNode* l = stk.top().first;
TreeNode* r = stk.top().second;
stk.pop();
if (!l and !r) continue;
if (!l or !r or l->val != r->val) return false;
stk.push({l->left, r->right});
stk.push({l->right, r->left});
}
return true;
}Iterative Postorder and Inorder Traversal
While iterative preorder traversal is straightforward, with postorder and inorder we run into a complication: we cannot simply swap the order of the lines as with the recursive implementation. In other words, the following does not yield a postorder traversal:
...
stk.push(node->right);
stk.push(node->left);
process(node);
...The node is still processed before its children, which is not what we want.
The workaround, once again emulating the recursive implementation, is to visit each node twice. We consider postorder traversal first. In the first visit, we only push the children onto the stack. In the second visit, we do the actual processing.
The simplest way to do this is to enhance the stack with a "visit number flag". Implementation-wise, we change the stack to stack<pair<TreeNode*, int>> so that we can pass the flag along with each node. The iterative postorder looks like this:
void postorderTraversal(TreeNode* root) {
stack<pair<TreeNode*,int>> stk; //node, visit #
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->right, 0});
stk.push({node->left, 0});
} else { //visit == 1
process(node);
}
}
}Note the order in which the nodes are added to the stack when visit == 0. The parent ends up under its children, with the left child on top. Since it is the first time that the children are added to the stack, their visit-number flag is 0. For the parent, it is 1.
For simplicity, I also follow the convention to always immediately call pop after extracting the top element from the stack.
The same approach also works for inorder traversal (that's the point). Here is a version where we visit each node three times: one to push the left child, one to process the node, and one to push the right child.
//3-visit version
void inorderTraversal(TreeNode* root) {
stack<pair<TreeNode*,int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->left, 0});
} else if (visit == 1) {
stk.push({node, 2});
process(node);
} else { //visit == 2
stk.push({node->right, 0});
}
}
}In fact, the second and third visits can be merged together: processing the node does not modify the stack, so the two visits are followed one after the other anyway. Here is my preferred version:
//2-visit version
void inorderTraversal(TreeNode* root) {
stack<pair<TreeNode*,int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->left, 0});
} else { //visit == 1
process(node);
stk.push({node->right, 0});
}
}
}For completeness, here is the version found in most of my top Google hits (see this for a nice explanation):
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr or !stk.empty()) {
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
process(curr);
curr = curr->right;
}
} While it is shorter, it cannot be easily converted to postorder traversal, so it is not as flexible. Also, I find it easier to follow the execution flow with the visit-number flag.
Inorder traversal practice problems
A solution (follow the link for the statement and examples):
int kthSmallest(TreeNode* root, int k) {
int count = 1;
stack<pair<TreeNode*, int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->left, 0});
} else { //visit == 1
if (count == k) return node->val;
count++;
stk.push({node->right, 0});
}
}
return -1;
}A solution:
bool isValidBST(TreeNode* root) {
int lastVal;
bool init = false;
stack<pair<TreeNode*, int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->left, 0});
} else { //second visit
if (!init) {
init = true;
lastVal = node->val;
} else {
if (node->val <= lastVal) return false;
lastVal = node->val;
}
stk.push({node->right, 0});
}
}
return true;
}Postorder traversal practice problems
This problem asks to check if a binary tree is balanced. It requires passing information back from the children to the parent node in a postorder traversal. Passing information from the children to the parent is easy with recursion. It can be done both with return values or with parameters passed by reference. For this problem we need to pass two things: a bool indicating if the subtree is balanced, and an int indicating its height. I use a reference parameter for the latter (returning a pair<bool,int> would be cleaner).
bool isBalancedRec(TreeNode* root, int& height) {
if (!root) {
height = 0;
return true;
}
int lHeight, rHeight;
bool lBal = isBalancedRec(root->left, lHeight);
bool rBal = isBalancedRec(root->right, rHeight);
height = max(lHeight, rHeight) + 1;
return lBal && rBal && abs(lHeight - rHeight) <= 1;
}
bool isBalanced(TreeNode* root) {
int height;
return isBalancedRec(root, height);
}Passing information from the children to the parent in an iterative implementation is more intricate. There are three general approaches:
- Use a hash table mapping each node to the information.
This is the easiest way, but also the most expensive.
While the asymptotic runtime is still linear, hash tables generally have significant constant factors.
bool isBalanced(TreeNode* root) {
stack<pair<TreeNode*, int>> stk;
stk.push({root, 0});
unordered_map<TreeNode*, int> height;
height[NULL] = 0;
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->right, 0});
stk.push({node->left, 0});
} else { // visit == 1
int lHeight = height[node->left], rHeight = height[node->right];
if (abs(lHeight - rHeight) > 1) return false;
height[node] = max(lHeight, rHeight) + 1;
}
}
return true;
}- Add a field to the definition of the node structure for the information needed.
Then, we can read it from the parent node by traversing the children's pointers.
In Leetcode we cannot modify the TreeNode data structure so, to illustrate this approach, I build a new tree first with a new struct:
struct MyNode {
int val;
int height;
MyNode *left;
MyNode *right;
MyNode(TreeNode* node): val(node->val), height(-1), left(NULL), right(NULL) {
if (node->left) left = new MyNode(node->left);
if (node->right) right = new MyNode(node->right);
}
};
bool isBalanced(TreeNode* root) {
if (!root) return true;
MyNode* myRoot = new MyNode(root);
stack<pair<MyNode*, int>> stk;
stk.push({myRoot, 0});
while (!stk.empty()) {
MyNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
if (visit == 0) {
stk.push({node, 1});
stk.push({node->right, 0});
stk.push({node->left, 0});
} else { // visit == 1
int lHeight = 0, rHeight = 0;
if (node->left) lHeight = node->left->height;
if (node->right) rHeight = node->right->height;
if (abs(lHeight - rHeight) > 1) return false;
node->height = max(lHeight, rHeight) + 1;
}
}
return true;
}- Pass the information through an additional stack.
This is the most efficient, but one must be careful to keep both stacks in synch. When processing a node, that node first pops the information from its children, and then pushes its own info for its parent. Here is a solution (with eager NULL-pointer detection):
bool isBalanced(TreeNode* root) {
if (!root) return true;
stack<pair<TreeNode*, int>> stk;
stk.push({root, 0});
stack<int> heights;
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (visit == 0) {
stk.push({node, 1});
if (node->right) stk.push({node->right, 0});
if (node->left) stk.push({node->left, 0});
} else { // visit == 1
int rHeight = 0, lHeight = 0;
if (node->right) {
rHeight = heights.top();
heights.pop();
}
if (node->left) {
lHeight = heights.top();
heights.pop();
}
if (abs(lHeight - rHeight) > 1) return false;
heights.push(max(lHeight, rHeight) + 1);
}
}
return true;
}This problem also requires passing information from the children to the parent in a postorder traversal. Here is a solution using the third approach again, but this time with lazy NULL-pointer detection. Note that we push a 0 to the depths stack when we extract a NULL pointer from the main stack, and during processing we always do two pops regardless of the number of non-NULL children:
int diameterOfBinaryTree(TreeNode* root) {
stack<pair<TreeNode*,int>> stk;
stk.push({root, 0});
stack<int> depths;
int res = 0;
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) {
depths.push(0);
continue;
}
if (visit == 0) {
stk.push({node, 1});
stk.push({node->right, 0});
stk.push({node->left, 0});
} else { //visit == 1
int rDepth = depths.top();
depths.pop();
int lDepth = depths.top();
depths.pop();
int depth = max(lDepth, rDepth) + 1;
depths.push(depth);
int dia = lDepth + rDepth;
res = max(res, dia);
}
}
return res;
}- https://leetcode.com/problems/binary-tree-tilt/
- https://leetcode.com/problems/most-frequent-subtree-sum/
- https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
Traversals in n-ary Trees
So far, we have looked at binary trees. In an n-ary tree, each node has an arbitrary number of children.
struct Node {
int val;
vector<Node*> children;
Node(int val): val(val), children(0) {}
};For n-ary trees, preorder traversal is also straightforward, and inorder traversal is not defined.
For postorder traversal, we can use a visit-number flag again. Two visits suffice for each node: one to push all the children into the stack, and another to process the node itself. I do not include the code here because it is very similar to the binary tree case.
Consider a more complicated setting where we need to compute something at the node after visiting each child. Let's call this "interleaved traversal". I use process(node, i) as placeholder for the computation done before visiting the i-th child. Here is the recursive implementation and the corresponding iterative one using visit-number flags.
//recursive
void interleavedTraversal(Node* root) {
if (!root) return;
int n = root->children.size();
for (int i = 0; i < n; i++) {
process(root, i);
interleavedTraversal(root->children[i]);
}
}
//iterative
void interleavedTraversal(Node* root) {
stack<pair<TreeNode*, int>> stk;
stk.push({root, 0});
while (!stk.empty()) {
TreeNode* node = stk.top().first;
int visit = stk.top().second;
stk.pop();
if (!node) continue;
int n = node->children.size();
if (visit < n) {
stk.push({node, visit+1});
process(node, visit);
stk.push({node->children[visit], 0});
}
}
}N-ary tree practice problems
- https://leetcode.com/problems/n-ary-tree-preorder-traversal/
- https://leetcode.com/problems/n-ary-tree-postorder-traversal/
An Alternative Way of Passing the Visit Flag
The common framework to all our solutions has been to pass a visit-number flag along with the nodes on the stack. User "heiswyd" on Leetcode posted here an alternative way to pass the flag implicitly: initially, it pushes each node on the stack twice. Then, it can distinguish between the first visit and the second visit by checking whether the node that has just been extracted from the stack matches the node on top of the stack. This happens only when we extract the first of the two occurrences. Post-order traversal looks like this:
void postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
stk.push(root);
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
if (!node) continue;
if (!stk.empty() and stk.top() == node) {
stk.push(node->right);
stk.push(node->right);
stk.push(node->left);
stk.push(node->left);
} else {
process(node);
}
}
}It is cool, but I prefer passing the flag explicitly for clarity.
Return to the blog's main page.