Iterative Binary Tree Traversal, Solving Microsoft Interview Question.

Question: Traverse a Binary Tree Iteratively(Inorder).

Traditional Method

The Traditional Method is to traverse a binary tree using Depth First Traversal Method.

    var inorderTraversal = function(root) {
        let res = [];
        dfs(root,res);
        return res;
    };

    function dfs(root,res){
        if(root == null) return null;
        if(root.left) dfs(root.left,res);
        res.push(root.val);
        if(root.right) dfs(root.right,res);
    }

The interviewer specially asked for Iterative Traversal. It becomes a bit tricky.

To understand how to convert from recursive to iterative, first let's understand how inorder traversal works.

Inorder Travesal

It's a two-step process,
1> If there's a left node, go to the left node.
2> After visited the left node, if there's a right node, go towards the right node.

So to traverse it iteratively, we need a data structure that will store all the nodes. But nodes need to be stored in a particular order of starting from root node to its left-most child node. And then when we reach the lest-most child node, we want left-most child node, the first to be evaluated.

So a data structure where we can keep on push node in the order they were accessed, and then pop the recently accessed node.

This naturally leads to a stack data structure.

Iterative Appraoch

Then one we remove pop a node from the stack, we look if it has the right node? If it has a right node we push that node stack and again we go on the journey to find the leftmost child for that node because of the inorder traversal rule.

So the process are :
1 > Push a node on stack and move left.
2 > If there are no more left child node, pop the latest pushed node.
3 > For the popped node, evaluated it and then check if it has right chid node.
4 > If it has the right child node, then push the right node and find it's leftmost child node.

I know that's too much so here's a gif I fond:

    var inorderTraversal = function(root) {
        let stack = [], res = [];
        if (root === null) {
            return res;
        }

        let curr = root;
        while(curr !== null || stack.length) {
            while (curr !== null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            res.push(curr.val);
            curr = curr.right;        
        }
        return res;
    };

I hope you understood my explanation :)

Github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/IterativeBinaryTreeTravesal.js