in-order-traversal-binary-tree.js

// inOrder Traversal
// Left - Data - Right

// Note that the Data is processed only after LEFT is processed.
// Same way, Right is processed only after Left and Data are processed.
// So, the key here is, the moment a LEFT occurs, push it into the stack for later
// processing. 
// So, when a Node is popped off the stack, its not guaranteed to have a RIGHT.
// So, when we hit a LEAF node, we pop the immediate previous ancestor, but,
// This is not guaranteed to have a RIGHT. Just process it.
// If it has a RIGHT, process it.
// Else, continue popping off elements from the stack, until either we hit a Node (parent)
// that has a RIGHT subtree, or the stack goes empty.

// Possible combinations are:
// 1. L-D
    // Left is present. Right is absent.
    // Since left is present, push into the stack
    // Start to Process the Left SubTree
    // Later, when this node is popped off the stack, process its data.
// 2. D-R
    // Process the Data
    // Since there is no Left, no need to push into stack
    // Start processing the RIGHT
// 3. D
    // No LEFT and NO right.
    // NO need to push into the stack.
    // Just process Data.
    // Then pop off the previous immediate ancestor off the stack and process it.
// 4. L-D-R
    // Left exists, so push into the stack (so that Data and RIGHT can be processed)
    // Start processing the LEFT
function inOrder(root) {
    if (root === null) {
        return null;
    }
    
    let currentNode = root;
    let hasLeft = false;
    let hasRight = false;
    let prevNode = null;
    
    const stack = [];
    const result = [];
    
    while ((currentNode !== null) && (typeof currentNode !== 'undefined')) {
        hasLeft = (currentNode.left !== null);
        hasRight = (currentNode.right !== null);
        
        // if it has a LEFT, push into stack
        // continue processing LEFT subtree
        if (hasLeft) {
            stack.unshift(currentNode);
            currentNode = currentNode.left;
            continue;
        }
        
        // At this point, LEFT is absent, so process DATA
        // Then proceed to check if a RIGHT exists
        result.push(currentNode.val);
        
        // if a RIGHT exists, we process it only after DATA is processed (above)
        // also, its processed only because a LEFT did not exist
        // and RIGHT exists. Else, RIGHT usually gets processed only when the Node
        // is popped off the stack
        if (!hasLeft && hasRight) {
            currentNode = currentNode.right;
            continue;
        }
        
        // At this point, The Data is processed
        // The node neither has a LEFT nor RIGHT => its a LEAF
        // start processing immediate ancestors
        if (!hasLeft && !hasRight) {
            // since we are not guaranteed to get a prev ancestor that has a RIGHT
            // we process its Data, but continue to pop off elements from the stack
            // until we either hit a Node that has a RIGHT to process, or the stack
            // goes empty.
            do {
                // get the immediate prev ancestor
                prevNode = stack.shift();
                
                // if its NULL / UNDEFINIED, the stack is empty
                // terminate inner loop with the break
                // but also set currentNode as NULL to terminate outer loop
                if (!prevNode) {
                    currentNode = null;
                    break;
                }
                
                // Node exist, process its Data 1st (before checking for a RIGHT)
                // since its L-D-R
                result.push(prevNode.val);
                
                // check if a RIGHT exists,
                // if it exist, terminate inner loop
                // continue outer loop by setting the currentNode as RIGHT
                if (prevNode.right !== null) {
                    currentNode = prevNode.right;
                    prevNode = null;
                    break;
                }
    
                // Right did not exist, so reset prevNode to null
                // so that the inner loop continues to pop off next element off the stack
                prevNode = null;
            } while (prevNode === null);
        }
    }
    
    return result;
}