13 Ways to Traverse a Tree: Recursion vs Iteration

To understand recursion, you must understand recursion. I will show you 13 different ways to traverse a tree to compare recursive and iterative implementations. This way, we will kill two birds with one stone: recursion and .

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.”

Recursion, iteration and how to traverse a tree are useful skills to have and common in interview questions. Do not risk failing your next job interview because you didn’t take the time to read one article.

I assume you have basic coding skills and are familiar with stacks, queues, recursion, and loops. If this seems too advanced for you, check  where I have listed some resources to get you started.

What Is a Tree?

Trees are data structures that organize data hierarchically. They are defined recursively from a root node, that contains the data that needs to be stored and pointers to its children.

• , for efficient searches on sorted data.
•  to store database indexes.
•  to implement .
• General trees to implement .
• Etc.

There is no point in storing information if you do not know how to access it.

You are going to learn infinitely more by doing than by reading or watching.

13 Ways To Traverse a Tree

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 }

For the complexity analysis, we will assume that we will traverse a tree of height H that contains N nodes.

1. Pre-order Traversal – Recursive

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Solution

• Base condition: As long as the node is not null,
• Recursive relationship: you process it (for instance, print its value), and then call the same function in the left and right children.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        // helperB(root, sol);
        return sol;
    }
    
    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            sol.push_back(n->val);
            helperA(n->left, sol);
            helperA(n->right, sol);
        }
    }
    
    void helperB(TreeNode* n, vector<int>& sol){
        sol.push_back(n->val);
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);
    }
};

Option A. Every function call will test whether the node it receives is null or not. Then, it will trigger two recursive calls. This option will result in a larger stack.

Option B. The function assumes that the node is not null. It will generate a recursive call only if the left/right child is not null. The function will execute more if statements but make less recursive calls.

There is no right or wrong solution here without more context. In an interview setting, discuss both options. It will show that you care about your code and think of the implications of what you write.

Your priority should be writing readable and maintainable working code. Only focus on this level of detail when you have profiled your code and have proof that these lines of code make a big impact on the overall performance. Don’t guess. Remember.

“Premature optimization is the root of all evil.”

Complexity

Challenge

Given an n-ary tree, return the preorder traversal of its nodes’ values.

To make you think

A natural follow-up to this problem is to generalize it to trees with N children. Before opening the link to Leetcode, try to first model the nodes yourself. Some interesting questions are:

• What data structures are suitable to store at most N children?
• If you don’t know the maximum number of children a node can have, can you still use this data structure? What other options do you have?
• What if you want to make a generic tree that works for different data types? The answer to this question will depend on your programming language: templates for C++, Generics for Java, etc.

2. Pre-order Traversal – Iterative

Solution

• First, we visit the root of the tree – add it to the solution.
• Then we process the left child, and finally the right child.
• We will need to create and handle the stack ourselves instead of relying on recursive calls.
• A stack is a Last-In-First-Out data structure. Therefore we have to push the items in the reverse order we want to extract them.

1. The iterative algorithm begins by adding the root of the tree to a stack s.
2. As long as s is not empty, we pop elements from it. We add them to the data structure that represents the solution because we want to process the parent node before its children.
3. We push the children to s. First the right child and then the left child. This way, we will pop the left one before the right one, which is exactly the order in which we want to process them.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            auto t = s.top(); s.pop();
            sol.push_back(t->val);
          
            if(t->right)
                s.push(t->right);
            if(t->left)
                s.push(t->left);
        }
        return sol;
    }
};

Complexity

Challenge

3. In-Order Traversal – Recursive

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Solution

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }
    
    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            sol.push_back(n->val);
            helperA(n->right, sol);
        }
    }
    
    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);
      
        sol.push_back(n->val);
      
        if(n->right)
            helperB(n->right, sol);        
    }
};

Complexity

4. In-Order Traversal – Iterative

Traverse a tree using in-order traversal. No recursion allowed.

Solution

• We call the helper function on the root.
• This calls itself on the left child of the root.
• This calls itself on the left child of the left child of the root.
• This process of moving to the left child repeats until we get to a node k that has no left child. It is only then when we process k that we continue by exploring its right child.
• The implicit stack has stored all the nodes between the root and k. Once we are done with k’s right child, the next node to process will be extracted from the implicit stack.

We need to mimic this with our stack. Let’s call it s.

• To kick-off the tree traversal, we add the root of the tree to s.
• If the root does not have a left child or we have finished exploring the root’s left subtree, we process the root and move to its right child.
• Otherwise, this is the case where we keep moving left:
  
  1. We add the root to the stack – to process it later
  2. We move to the left

From this algorithm, it looks like we need a stack and a pointer n to mark the node we are currently at. If n becomes null, it means we are done exploring a subtree and need to query the stack for the next node to process. If the stack is empty, we have processed all nodes.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        stack<TreeNode*> s;
        TreeNode* n = root;
        while(n || !s.empty()) {
            const bool hasToGoRight = !n;
            if(hasToGoRight){
                auto top = s.top(); s.pop();
                sol.push_back(top->val);
                n = top->right;
            } else {
                s.push(n);
                n = n->left;
            }
        }
        return sol;
    }
};

Complexity

5. Post-Order Traversal – Recursive

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Solution

In a post-order traversal, we first visit the left child, then the last child and finally the root of the tree, hence the name post-order. This algorithm requires a minimal change with respect to the pre-order and in-order traversals that we have just seen.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        vector<int> sol;
        helperA(root, sol);
        //helperB(root, sol);
        return sol;
    }
    
    void helperA(TreeNode* n, vector<int>& sol){
        if(n){
            helperA(n->left, sol);
            helperA(n->right, sol);
            sol.push_back(n->val);
        }
    }
    
    void helperB(TreeNode* n, vector<int>& sol){
        if(n->left)
            helperB(n->left, sol);
        if(n->right)
            helperB(n->right, sol);        
        sol.push_back(n->val);
    }
};

Complexity

Challenge

6. Post-Order Traversal – Iterative

Traverse a binary tree using post-order traversal. No recursion allowed.

Solution

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();
            
            sol.push_back(top->val);
            
            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }
      
    	for(auto x : sol)
          cout<<x<<endl;
        return sol;
    }
};

Above all, it is worth noting is that sometimes it is useful to play with similar problems to try to get a solution to the problem you are trying to solve.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root)
            return {};
        stack<TreeNode*> s;
        s.push(root);
        vector<int> sol;
        while(!s.empty()){
            auto top = s.top(); s.pop();
            
            sol.push_back(top->val);
            
            if(top->left)
                s.push(top->left);
            if(top->right)
                s.push(top->right);
        }
      
    	reverse(sol.begin(), sol.end());        
        return sol;
    }
};

Complexity

• Time: we are doing constant work per element. Reversing a vector is also a linear-time operation.
• Space: the space complexity is linear, whether we use one or two stacks.7. Morris Traversal – How to Traverse a Tree Using Constant Space

7. Morris Traversal – How to Traverse a Tree Using Constant Space

Solution

We will have two pointers: current and explorer. We will use explorer to move around the tree and build links from some leaves back to current. Current can only move left if we have previously built a link from its predecessor back to current. This is the only thing I have “memorized” about Morris. From this, I can draw a tree and rebuild the algorithm every time.

This image has all the links that we will need to build. However, we do not need to keep any of them: as soon as we are done using a bridge, we destroy it.

1. First, we set current to root.
2. If current does not have a left child, we add current to the solution and move to its right child.
3. Otherwise:
   1. We find current’s predecessor, using explorer.
   2. If there is already a link between explorer and current, we break it, add current to the solution and move to current’s right child.
   3. Otherwise, we build a link between explorer and current and move current to its left child.
4. Go back to 2 until current becomes null.

Example

• Current starts at 7.
• Using explorer, we find its predecessor, 6, and link it back to current.
• We move current to 4.
• Using explorer, we find its predecessor, 4, and link it back to current.
• We move current to 2.
• Current has no left child, so our solution becomes: [2].
• We move to current’s right, 4.Using explorer, we find its predecessor, 2.
• Since explorer (2) is already linking to current (4), we break this link and add 4 to our solution: [2, 4]
• We move current to its right child, 5.
• Current has no left child, so we add it to our solution [2, 4, 5] and move to its right child
• We are in the same situation as step 9. Our solution becomes [2, 4, 5, 6] and current is back at 7.
• Etc.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> sol;
		auto current = root;
        while(current){
            if(!current->left) {
                sol.push_back(current->val);
                current = current->right;
            } else {
                TreeNode* explorer = current->left;
              //Find currents predecessor
                while(explorer->right && explorer->right != current) {
                    explorer = explorer->right;
                }
                
              //Is it linking back to current?
                if(explorer->right == current) {
                    explorer->right = nullptr;
                    sol.push_back(current->val);
                    current = current->right;
                } else {
                    explorer->right = current;
                    current = current->left;
                }
            }
        }
        return sol;
    }
};

//Is it linking back to current?
if(explorer->right == current) {
  explorer->right = nullptr;
  current = current->right;
} else {
  sol.push_back(current->val);
  explorer->right = current;
  current = current->left;
}

Complexity

Challenge

8. Level Order Traversal – Iterative

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Solution

• After we push all the nodes in a level, we introduce a special type of node that indicates that we need a new level – for example, a nullptr.
• Before we start processing the queue, we take note of its size s – the elements at that level. We create a new level after we have process s elements.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        queue<TreeNode*> q;
        q.push(root);
        
        while(!q.empty()){
            int size = q.size();
            vector<int> partial;
            while(size-->0){
                auto n = q.front();
                partial.push_back({n->val});
                q.pop();
                if(n->left)
                    q.push({n->left});
                if(n->right)
                    q.push({n->right});
            }
            sol.push_back(partial);
        }
        return sol;
    }
};

Complexity

In the case of a full tree (every node has two children except for the leaves) of height H, the maximum number of nodes in a level will occur at the last level (the leaves), being this 2^H. For this type of tree, H = log2(N).

Challenge

9. Level-order Traversal – Recursive

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Solution

Always keep in mind the three basic ways to traverse a tree: pre-order, in-order and post-order. This problem is a pre-order tree traversal in disguise.

The only extra is that you want to put nodes that are at the same depth together. This can be easily achieved using a variable to keep track of the current level you are exploring.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        
        //Here is where the magic happens
        map<int, vector<int>> levels;
        helper(root, levels);
      
        //Here we create the solution in the expected data structure
        vector<vector<int>> sol;
        for(auto it = levels.begin(); it != levels.end(); ++it){
          sol.push_back(it->second);
        }
        return sol;
    }
    
    void helper (TreeNode* n, map<int, vector<int>> &levels, int depth = 0){
        levels[depth].push_back(n->val);
        
        if(n->left)
            helper(n->left, levels, depth + 1);
        
        if(n->right)
            helper(n->right, levels, depth + 1);
    }
};

Complexity

10. Level-Order Zigzag Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

Solution

You are right. This is a level-order traversal. The only extra is that we have to process some levels from left to right and others from right to left. We can achieve this easily with two stacks, s1 and s2.

1. Firstly, we create a new partial solution – the solution for the new level.
2. We pop the stack s1 and add this element to the partial solution.
3. The next level will be explored from right to left. Therefore, we add first the left child and the right child to the other stack s2
4. .We keep processing elements from s1 until it is empty.
5. In the next iteration, we will process elements from s2 to complete the next level from left to right.
6. When we process nodes from s2, we first add their right child and then the left child – LIFO for the next level.
7. We do this until both stacks are empty.

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(root);
        while(!s1.empty() || !s2.empty()){
            vector<int> partial;
            while(!s1.empty()){
                auto top = s1.top();
                partial.emplace_back(top->val);
                s1.pop();
                if(top->left)
                    s2.push(top->left);
                if(top->right)
                    s2.push(top->right);
            }
            if(!partial.empty()){
                sol.push_back(partial);
                partial.clear();
            }
            while(!s2.empty()){
                auto top = s2.top();
                partial.emplace_back(top->val);
                s2.pop();
                if(top->right)
                    s1.push(top->right);
                if(top->left)
                    s1.push(top->left);
            }
            if(!partial.empty()){
                sol.push_back(partial);
            }
        }
        return sol;
    }
};

Complexity

Challenges

11. Side View of a Tree

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Solution

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root)
            return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> sol;
        while(!q.empty()){
            int size = q.size();
            for(int i = 1; i <= size; ++i){
                auto top = q.front();
                if(i == size){
                    sol.push_back(top->val);
                }
                if(top->left)
                    q.push(top->left);
                if(top->right)
                    q.push(top->right);
                q.pop();
            }
        }
        return sol;
    }
};

Complexity

Challenges

• Solve this problem recursively
• Print the left side instead of the right side
• Print the leaves

12. Vertical-order traversal – Recursive

Given a binary tree, return the vertical order traversal of its nodes’ values.

Solution

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root)
        return {};
        
        map<int, vector<pair<int, int>>> distances;
        helper(root, 0, 0, distances);
        
        vector<vector<int>> sol;
        for(auto x : distances){
          //Using a lambda function to ensure nodes appear in the expected order
            sort(x.second.begin(),
                 x.second.end(), 
                 [] (pair<int,int> &a, pair<int,int> &b) {
                    if(a.first==b.first)
                        return a.second<b.second;
                    else
                        return a.first<b.first;
                    }
                );
            vector<int> v;
            for(auto y : x.second){
                v.push_back(y.second);
            }
            sol.push_back(v);
        }
        return sol;
    }
  
  void helper(TreeNode* root, int hd, int c, map<int,vector<pair<int,int>>> &distances){
        if(!root)
            return;
        distances[hd].push_back({c, root->val});
    
        helper(root->left, hd-1, c+1, distances);
        helper(root->right, hd+1, c+1, distances);
    }
};

Complexity

13. Vertical-order traversal – Iterative

Given a binary tree, return the vertical order traversal of its nodes’ values.

Solution

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int,int>>> distances;
        queue<pair<TreeNode*, int>> q;
        int level = 0;
        q.push({root, 0});
        distances[0].push_back({level, root->val});
        
        while(!q.empty()) {
            const int size = q.size();
            level++;
            for(int i = 0; i < size; i++) {
				auto node = q.front().first;
				int sd = q.front().second; q.pop();
				
				if(node->left) {
					distances[sd-1].push_back({level, node->left->val});
					q.push({node->left,sd-1});
				}
				
				if(node->right) {
					distances[sd+1].push_back({level, node->right->val});
					q.push({node->right,sd+1});
				}
            }
        }
		
        vector<vector<int>> sol;
        for(auto it : distances) {
            vector<int> partial;
            sort(it.second.begin(), it.second.end());
           
            for(int i= 0; i < it.second.size(); i++) {
                partial.push_back(it.second[i].second);
            }
            sol.push_back(partial);
        }
        
        return sol;
    }
};

Complexity

Conclusions

• In general, it is not trivial to translate a recursive algorithm into an iterative. However, this is trivial for  functions.
• Recursive solutions can lead to stack overflow. Always consider iterative solutions (limited by RAM size).
• Some problems have straightforward recursive solutions and complicated iterative implementations.
• Recursive solutions tend to be slower because of the stack calls. However, your focus should be on having a working code that is maintainable and readable. Only optimize after using a profiler and finding the real bottlenecks

As I have said before, it is not about solving a million problems or spending a million hours. What is important is what you get out of each hour. We have also seen that from a seemingly simple problem we have been able to extract a lot.

“No problem is too small or too trivial if we can really do something about it.”

The aim of this entry is to make you think about each problem. We have seen 13 ways to traverse a tree. We have work on recursive and iterative implementations. You have become smarter by going through this article. As the next logical step, I invite you to read my article on .

If you found this article helpful, please share it. Chances are more people will find it useful too. You can help someone pass their exams, a job interview, or get them unblocked at work.

PS: I hope you found this useful. If so, like and share this article, visit my blog , and let's connect on .