pre-order-traversal-binary-tree.js

// A pre-order traversal means Data - LEFT - RIGHT
// So, the possible combinations are
// 1. D-L 
        // No Right => Process Node and proceed with Left SubTree
        // No need to push into a stack for later processing (as there is no RIGHT)
// 2. D-R
        // No Left => Process Node and proceed with Right SubTree.
        // No need to push into a stack for later processing (as RIGHT exists)
        // and RIGHT is being processed currently (due to absence of a LEFT)
// 3. D
        // No Left, No Right => Process Node and pop off any previous element from stack
        // No need to push into a stack for later processing (No Left nor RIGHT)
        // In this case, when a previous Node is popped off the stack, its guaranteed
        // to have a RIGHT
// 4. D-L-R
        // Has Left and Right.
        // 1. Process the Node
        // 2. Push the processed Node onto Stack (since RIGHT exists)
        // 3. Start Processing the LEFT subtree
        // 
function preOrder(root) {
    if (root === null) {
        return null;
    }
    
    const result = [];

    // The JS array resembles a stack when an element is pushed in using unshift
    // and element is popped out using shift.
    // Thereby inserts and deletes happen at the start of the array.
    const stack = [];

    let currentNode = root;
    let hasLeft = false;
    let hasRight = false;
    let prevNode = null;
    
    while ((currentNode !== null) && (typeof currentNode !== 'undefined')) {
        // process the currentNode
        result.push(currentNode.val);
        
        hasLeft = (currentNode.left !== null);
        hasRight = (currentNode.right !== null);
        
        // if a RIGHT and LEFT exists, by order we would be processing LEFT 1st.
        // So, to get back to later processing of the RIGHT, we push it into a Stack
        // A stack is used here, cos we want the most recently pushed element.
        if (hasLeft && hasRight) {
            stack.unshift(currentNode);
        }
        
        // if It had a LEFT, process it immediately (don't even check if a right exists)
        // This is because the order of processing is D-L-R
        // And, if a RIGHT exists, it would eventually be processed when the element is
        // popped off the stack
        if (hasLeft) {
            currentNode = currentNode.left;
            continue;
        }
        
        // if it did not have a LEFT but had a RIGHT
        if (!hasLeft && hasRight) {
            currentNode = currentNode.right;
            continue;
        }
        
        // No left & No right => Its a leaf
        // So pop off an element from the top of the stack
        // This popped element would be the most immediate ancestor that has a RIGHT
        // if the popped element is NULL / UNDEFINED => stack is empty
        // Break the iteration (as there is nothing more to iterate)
        // Else reset currentNode to be the poppedElement's RIGHT and proceed.
        if (!hasLeft && !hasRight) {
            prevNode = stack.shift();
            
            if (!prevNode) {
                currentNode = null;
                break;
            }
            
            currentNode = prevNode.right;
            prevNode = null;
        }
    }
    
    return result;
}