post-order-traversal-binary-tree.js

// Post Order traversal => Left - Right - Data
// L-R-D
// Possible combinations
// 1. L-D
    // Only Left exists. Right is absent. Since the Node has to be processed after the
    // LEFT is processed, its pushed into the stack for later processing.
    // Continue process the LEFT subtree.
// 2. R-D
    // Only Right exists. Left is absent. Since the Node has to be processed after the
    // RIGHT is processed, its pushed into the stack for later processing.
    // Continue process the RIGHT subtree (since LEFT is absent).
// 3. D
    // No Left nor right. Just process the Node.
    // Since its the LEAF, pop out elements from the top of stack (immediate ancestors)
    // And process them for both the RIGHT subtree and their NODE
    // When popping elements, if the popped Node is NULL / UNDEFINED, then the stack
    // is empty.
    // Else, if not empty, there are 2 options: A) the Node has no right
    // B) The Node has a right. If the node has no right, just process the data
    // and continue popping elements off the stack, until we hit a NODE with RIGHT
    // or the STACK goes empty.
// 4. L-R-D
    // This has both the LEFT and RIGHT. The LEFT has to be processed 1st, followed
    // By the RIGHT and then the Data of the Node. So push it into the stack.
    // Per order, since LEFT is 1st, start by processing the LEFT subtree.
// Notice that, by popping an element off the stack, it does not guarantee itself
// to have a RIGHT.
// Also notice, by presence of either of LEFT or RIGHT subtree, we push the Node
// to the stack.
// Also, when attempting to pop elements off the stack, we only PEEK 1st.
// PEEKING is done cos, we need to process the RIGHT subtree and then refer back to
// the stack, for the same element, to process the NODEs data.
// SO we pop elements off the stack only when it DOES NOT have a RIGHT subtree.
function postOrder(root) {
    if (root === null) {
        return null;
    }
    
    const result = [];
    const stack = [];
    
    let currentNode = root;
    let hasRight = false;
    let hasLeft = true;
    let prevNode = null;
    
    while (currentNode !== null) {
        // check for the LEFT and RIGHT subtrees
        hasLeft = (currentNode.left !== null);
        hasRight = (currentNode.right !== null);
        
        // even if one of them is present, push into stack
        // since the Node's data is the last to be processed.
        if (hasLeft || hasRight) {
            stack.unshift(currentNode);
        }
        
        // if there is a LEFT, per the order, L-R-D, process it.
        if (hasLeft) {
            currentNode = currentNode.left;
            continue;
        }
        
        // if control comes here, then the Node has NO LEFT subtree
        // if the right subtree exists, process it
        if (!hasLeft && hasRight) {
            currentNode = currentNode.right;
            continue;
        }
        
        // if the control came here, then the Node has neither LEFT nor RIGHT
        // its a LEAF. So process it
        // Then PEEK the top element of the stack
        // if PEEKED element = NULL / UNDEFINED => stack is empty, break inner loop
        // reset currentNode = null (so that outer loop also breaks)
        // Check if the peeked element has a RIGHT
            // If No RIGHT, 
                // process it,
                // pop it out of stack
                // reset current pointer to prevNode and set prevNode to NULL
                // inner loop continues to peek next element off the stack
            // if a RIGHT exists,
                // check if currentNode !== prevNode.right
                    // if TRUE, set currentNode = prevNode.right
                    // break inner loop, so that outer loop continues
                // if currentNode === prevNode.right
                    // Then process the Node & pop it out of stack
                    // set the currentNode = prevNode
        if (!hasLeft && !hasRight) {
            result.push(currentNode.val);

            do {
                prevNode = stack[0];
                
                if (!prevNode) {
                    currentNode = null;
                    prevNode = null;
                    break;
                }
                
                if ((prevNode.right !== null) && (prevNode.right !== currentNode)) {
                    currentNode = prevNode.right;
                    prevNode = null;
                    break;
                }
                
                result.push(prevNode.val);
                stack.shift();
                // This is mainly needed for post-order traversal.
                // Solve a tree like
                // 4 Right skewed Node's with the Last Right skewed Node's Left existing.
                currentNode = prevNode;
                prevNode = null;
            } while (prevNode === null);
        }
    }
    
    return result;
}