Binary tree traversal without recursion

Tree traversal with recursion is simple but sometime you need to traverse without recursion because you want control on the traversal. Let’s say you want to pause for sometime and continue later.

e.g — Let’s say you want to create a iterator which will return data on calling next() method. In this case recursion won’t work.

In this article I am going to write a program which will traverse without recursion.

If you are looking for traversal with recursion or in simple way, visit this article — https://ujjwalkrgupta.medium.com/binary-tree-in-javascript-36a2c3d7c9d8

class Node {
    constructor(value) {
        this.data = value;
    }
}
class BinaryTree {
    constructor() {
        this.root = new Node(10);
        this.root.left = new Node(15);
        this.root.right = new Node(20);
    }
    inOrderTraverse() {
        const stack = [];
        let currentNode = this.root;
        do {
            if (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            else {
                currentNode = stack.pop();
                console.log(currentNode.data);
                currentNode = currentNode.right;
            }
        } while (stack.length > 0 || currentNode != null);
    }
    preOrderTraverse() {
        const stack = [this.root];
        while (stack.length > 0) {
            let node = stack.shift();
            console.log(node.data);
            if (node.left) {
                stack.push(node.left)
            }
            if (node.right) {
                stack.push(node.right)
            }
        }
    }    
    postOrderTraverse() {
        const stack1 = [this.root];
        const stack2 = [];
        while (stack1.length > 0) {
            let node = stack1.pop();
            if (node.left) {
                stack1.push(node.left)
            }
            if (node.right) {
                stack1.push(node.right)
            }
            stack2.push(node.data);
        }
        while (stack2.length > 0) {
            console.log(stack2.pop())
        }
    }
}
new BinaryTree().inOrderTraverse(); // 15 10 20
new BinaryTree().preOrderTraverse(); // 10 15 20
new BinaryTree().postOrderTraverse(); // 10 20 15