Iterative Binary Tree Traversals

April 18, 2022 • 7 min read

One common interview problem that commonly gets asked by interviewer is to write an in-order binary tree traversal algorithm. This deceptively simple problem in my own opinion is harder than it looks like. Although the recursive version is tidier, it hides the complexity that goes behind it. I, too, ended up memorizing those three lines, only to later realize that sometimes it was much harder to come up with a solution to a problem based on in-order traversal only using recursion.

Inorder Binary Search Tree Traversal

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);
    }
};

Recall our good ol' recursive in-order traversal.

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);
    }
};

Like a compiler, we can mechanically convert our function calls to use an explicit stack, but readibility/memoribility would suffer.

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);
        }
    }
};

The in-order traversal requires that we print the leftmost node first and the right most node at the end. So basically for each node we need to go as far as down and left as possible. So the line inorder(root->left) could be replaced with a while loop to have similar effect.

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;
        }
    }
};

Now we need to retrieve the top node and store it's right child if it exists

An iterative solution can help us solve multiple tree problems, and the same template could be used for multiple problems.

Recall our good ol' recursive in-order traversal.

Like a compiler, we can mechanically convert our function calls to use an explicit stack, but readibility/memoribility would suffer.

Now we need to retrieve the top node and store it's right child if it exists

An iterative solution can help us solve multiple tree problems, and the same template could be used for multiple 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;
        }
    }
};

Let's use the same template we created earlier to solve multiple leetcode problem using the same pattern

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.

Let's use the same template we created earlier to solve multiple leetcode problem using the same pattern

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();
    }
};

That’s it! I hope you enjoyed the explanation, not only we managed to understand inorder binary search tree traversal but also managed to solve handful leetcode problems as well and feel free to reach out to me on how I could improve its clarity. Next great steps after you think you’ve understood this is to try and implement the iterative solutions for preorder binary tree traversal and postorder binary tree traversal!

Happy coding.

← Configure Nginx Proxy Manager with Bitwarden Binary Search →

Inorder Binary Search Tree Traversal

Want more?