Iterative Binary Tree Traversals

April 18, 2022 • 7 min read

One of the common interview problems that frequently gets asked by interviewers is to write an inorder binary tree traversal algorithm. This problem may appear simple at first, but it is trickier than it appears. Although the recursive version is tidier, it hides the complexity that goes behind it. The recursive version may not always be the optimal solution to solve the problem. In this blog post, we will explore the iterative version of the inorder binary tree traversal algorithm.

Inorder Binary Search Tree Traversal

To start, let’s review the recursive version of the inorder binary search tree traversal algorithm.

inorderTraversal.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        //Traverse to the left most node
        inorder(root -> left);
        //Magic goes here
        cout << root -> val << endl;
        //Go to the right node
        inorder(root -> right);
    }
};

The inorder binary tree traversal algorithm requires that we print the leftmost node first and the rightmost node at the end. So for each node, we need to go as far down and left as possible.

The recursive version of the inorder traversal algorithm is simple to understand, but it has a drawback of using a stack that may cause a stack overflow error on large trees. Therefore, we will explore the iterative version of the inorder binary tree traversal algorithm using a stack.

inorderTraversal.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        stack<TreeNode*> nodes;
        //Traverse to the left most node
        inorder(root -> left);
        //Magic goes here
        cout << root -> val << endl;
        //Go to the right node
        inorder(root -> right);
    }
};

Here, we use a stack to store the left subtree nodes. We first traverse down to the leftmost node of the tree and push all the nodes along the way onto the stack. Once the leftmost node is found, we pop the node from the stack, process it, and then move to its right child. We repeat this process until the stack is empty.

inorderTraversal.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        stack<TreeNode*> nodes;
        
        //Traverse to the left most node
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        //Magic goes here
        cout << root -> val << endl;
        //Go to the right node
        inorder(root -> right);
        }
    }
};

inorderTraversal.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        stack<TreeNode*> nodes;
        
        //Traverse to the left most node
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        cout << root -> val << endl;
        //Go to the right node
        root = root->right;
        }
    }
};

We can create a template for the inorder binary tree traversal algorithm that we can use to solve multiple leetcode problems.

To start, let’s review the recursive version of the inorder binary search tree traversal algorithm.

The inorder binary tree traversal algorithm requires that we print the leftmost node first and the rightmost node at the end. So for each node, we need to go as far down and left as possible.

We can create a template for the inorder binary tree traversal algorithm that we can use to solve multiple leetcode problems.

inorderTraversal.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        //Traverse to the left most node
        inorder(root -> left);
        //Magic goes here
        cout << root -> val << endl;
        //Go to the right node
        inorder(root -> right);
    }
};

inOrderTemplate.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        cout << root -> val << endl;
        
        root = root->right;
        }
    }
};

We can use this template to solve multiple leetcode problems by just adding specific code to handle each problem’s specific requirements.

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) {
            return {};
        }
        stack<TreeNode*> nodes;
        vector<int> result;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        
        result.push_back(root->val);
        root = root->right;
        }
        return result;
    }
};

For leetcode problem Binary Tree Inorder Traversal, we need to return a list of node so rather than printing. This could be solved by storing the values in a list and returning it.

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }
        stack<TreeNode*> nodes;
        TreeNode* pre = nullptr;
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        if(pre && root->val <= pre->val) return false;
        pre = root;
        
        
        root = root->right;
        }
        return true;
    }
};

Similarly, in order to Validate Binary Search Tree could be solved by verifying if the in-order traversal is in ascending order

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        k--;
        if (k == 0) return root->val;
        
        
        root = root->right;
        }
        return -1;
    }
};

Find Kth Smallest Element in a BST by simply breaking at kth element

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        if (root->val == val) return root;
        
        
        root = root->right;
        }
        return NULL;
    }
};

Search in a Binary Search Tree becomes much simpler and one needs to simply check for val you are looking for.

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root, int val) {
        TreeNode* head = new TreeNode(-1);
        TreeNode* prev = head;
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        prev->right = root;
        prev = prev->right;
        root->left = NULL;
        
        
        root = root->right;
        }
        return head->right;
    }
};

Increasing Order Search Tree has similar intuition. Each time we meet a node, link it like a linked list using the right pointer. To facilitate the linking, create a dummy head

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    void recoverTree(TreeNode* head) {
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        TreeNode* root = head;
        TreeNode* prev = NULL;
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        if (prev != NULL && prev->val > root->val) {
            if (first == NULL) {
                first = prev;
            }
            second = root;
        }
        prev = root;
        
        root = root->right;
        }
        swap(first->val, second->val);
};

For Recover Binary Search Tree, the question boils down to to find "2" elements in a given sorted arrangement , such that both of these elements violate the "sorted" order, and swap them back to their original places.

inOrderTemplate.cpp

Solution.cpp

class Solution {
public:
    TreeNode* convertBST(TreeNode* root, int val) {
        if (!root) return NULL;
        TreeNode* head = root;
        int sum = 0;
        int current_val;
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->right;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        current_val = root->val;
        root->val = root->val + sum;
        sum += current_val;
        
        
        root = root->left;
        }
        return head;
    }
};

For Convert BST to Greater Tree, The solution is the modification of inorder travel. Namely, travel right subtree, change the root value, and travel left subtree.

We can use this template to solve multiple leetcode problems by just adding specific code to handle each problem’s specific requirements.

For leetcode problem Binary Tree Inorder Traversal, we need to return a list of node so rather than printing. This could be solved by storing the values in a list and returning it.

Similarly, in order to Validate Binary Search Tree could be solved by verifying if the in-order traversal is in ascending order

Find Kth Smallest Element in a BST by simply breaking at kth element

Search in a Binary Search Tree becomes much simpler and one needs to simply check for val you are looking for.

Increasing Order Search Tree has similar intuition. Each time we meet a node, link it like a linked list using the right pointer. To facilitate the linking, create a dummy head

For Convert BST to Greater Tree, The solution is the modification of inorder travel. Namely, travel right subtree, change the root value, and travel left subtree.

inOrderTemplate.cpp

class Solution {
public:
    void inorderTraversal(TreeNode* root) {
        if (!root) {
            return;
        }
        stack<TreeNode*> nodes;
        
        while(root || !nodes.empty()) {
            while(root) {
                nodes.push(root);
                root = root->left;
            }
        root = nodes.top(); nodes.pop();
        //Magic goes here
        cout << root -> val << endl;
        
        root = root->right;
        }
    }
};

Once you have realized the pattern, you could see Binary Search Tree Iterator problem has the exact same structure

Some initialization.
A while-loop with a condition that tells whether there is more.
The loop body gets the next value and does something with it.

BSTIterator.cpp

class BSTIterator {
    stack<TreeNode*> nodes;
    TreeNode* head;
    int result;
public:
    BSTIterator(TreeNode* root) {
        head = root;
        
        while(head) {
            s.push(head);
            head = head->left;
        }
    }
    
    int next() {
        head = s.top(); s.pop();
        result = head->val;
        if (head->right) {
            head = head->right;
            
            while(head) {
              s.push(head);
              head = head->left;  
            }
        }
        
        return result;
    }
    
    bool hasNext() {
        return !s.empty();
    }
};

In this blog post, we’ve seen how to perform iterative inorder traversal of a binary tree. Although the recursive version is tidier, it hides the complexity that goes behind it. An iterative solution can help us solve multiple tree problems, and the same template could be used for multiple problems.

← Configure Nginx Proxy Manager with Bitwarden Binary Search →

Inorder Binary Search Tree Traversal

Want more?