1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

POSTORDER TRAVERSAL ALGORITHM
═══════════════════════════════════════════════════════════════
 
    Input:  Root node of a binary tree (or null)
    Output: Sequence of node values in postorder
 
    Procedure POSTORDER(node):
        1. If node is null:
              Return (base case: nothing to visit)
        
        2. POSTORDER(node.left)   ← First, traverse left subtree
        
        3. POSTORDER(node.right)  ← Then, traverse right subtree
        
        4. VISIT(node)            ← Finally, process current node LAST
 
═══════════════════════════════════════════════════════════════
 
    Mnemonic: "LRV" — Left, Right, Visit
    
    The V (Visit) comes AFTER (post-) both subtrees, hence "POST-order"
    (as in "postfix" — the root goes at the end)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/**
 * Binary tree node definition
 */
interface TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;
}
 
/**
 * Postorder traversal - recursive implementation
 * 
 * Time Complexity:  O(n) - visits each node exactly once
 * Space Complexity: O(h) - recursive call stack depth equals tree height
 * 
 * Key Property: Children are always visited before their parent
 *               The root is ALWAYS the last node visited!
 * 
 * @param root - The root of the tree (or subtree)
 * @param result - Array to collect values (accumulator pattern)
 * @returns Array of values in postorder sequence
 */
function postorderTraversal<T>(
    root: TreeNode<T> | null,
    result: T[] = []
): T[] {
    // Base case: empty tree/subtree
    if (root === null) {
        return result;
    }
    
    // Step 1: LEFT - Traverse left subtree first
    postorderTraversal(root.left, result);
    
    // Step 2: RIGHT - Traverse right subtree second
    postorderTraversal(root.right, result);
    
    // Step 3: VISIT - Process current node LAST (the "POST" in postorder)
    result.push(root.value);
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Example usage
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree structure:
 *         1
 *        / \
 *       2   3
 *      / \
 *     4   5
 *
 * Postorder: Left subtree [4,5,2] → Right subtree [3] → Root [1]
 */
 
const tree: TreeNode<number> = {
    value: 1,
    left: {
        value: 2,
        left: { value: 4, left: null, right: null },
        right: { value: 5, left: null, right: null },
    },
    right: {
        value: 3,
        left: null,
        right: null,
    },
};
 
console.log(postorderTraversal(tree));
// Output: [4, 5, 2, 3, 1]
// Note: The root (1) is LAST! This is the defining property of postorder.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

POSTORDER TRAVERSAL EXECUTION TRACE
═══════════════════════════════════════════════════════════════════════════
 
Tree:           A
               / \
              B   C
             / \   \
            D   E   F
 
═══════════════════════════════════════════════════════════════════════════
Step  Call Stack          Action                    Result So Far
═══════════════════════════════════════════════════════════════════════════
 1    postorder(A)        Call postorder(B)         []
 2    └─postorder(B)      Call postorder(D)         []
 3      └─postorder(D)    Call postorder(null)      []
 4        └─null          Return (base case)        []
 5      └─postorder(D)    Call postorder(null)      []
 6        └─null          Return (base case)        []
 7      └─postorder(D)    VISIT D ★                 [D]
 8      └─postorder(D)    Return                    [D]
 9    └─postorder(B)      Call postorder(E)         [D]
10      └─postorder(E)    Call postorder(null)      [D]
11        └─null          Return (base case)        [D]
12      └─postorder(E)    Call postorder(null)      [D]
13        └─null          Return (base case)        [D]
14      └─postorder(E)    VISIT E ★                 [D, E]
15      └─postorder(E)    Return                    [D, E]
16    └─postorder(B)      VISIT B ★                 [D, E, B]
17    └─postorder(B)      Return                    [D, E, B]
18    postorder(A)        Call postorder(C)         [D, E, B]
19    └─postorder(C)      Call postorder(null)      [D, E, B]
20      └─null            Return (base case)        [D, E, B]
21    └─postorder(C)      Call postorder(F)         [D, E, B]
22      └─postorder(F)    Call postorder(null)      [D, E, B]
23        └─null          Return (base case)        [D, E, B]
24      └─postorder(F)    Call postorder(null)      [D, E, B]
25        └─null          Return (base case)        [D, E, B]
26      └─postorder(F)    VISIT F ★                 [D, E, B, F]
27      └─postorder(F)    Return                    [D, E, B, F]
28    └─postorder(C)      VISIT C ★                 [D, E, B, F, C]
29    └─postorder(C)      Return                    [D, E, B, F, C]
30    postorder(A)        VISIT A ★                 [D, E, B, F, C, A]
31    postorder(A)        Return                    [D, E, B, F, C, A]
═══════════════════════════════════════════════════════════════════════════
 
FINAL RESULT: [D, E, B, F, C, A]
 
KEY OBSERVATIONS:
★ Visit operations happen AFTER both children are fully processed
• Node A (root) is visited LAST (step 30) — defining property!
• Leaf nodes (D, E, F) are visited first
• Parent B is visited after children D and E (step 16)
• Maximum stack depth = 3 (tree height)
• Each node is visited only after ALL its descendants are visited

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/**
 * Postorder traversal - iterative implementation using TWO stacks
 * 
 * Key Insight:
 *   Preorder  = Root → Left → Right
 *   Modified  = Root → Right → Left  (swap left/right in preorder)
 *   Postorder = Left → Right → Root  (reverse of modified preorder!)
 * 
 * Algorithm:
 * 1. Do modified preorder (Root → Right → Left), pushing to stack2
 * 2. Pop everything from stack2 to get postorder
 * 
 * Time Complexity:  O(n)
 * Space Complexity: O(n) - both stacks together hold all nodes
 */
function postorderTwoStack<T>(root: TreeNode<T> | null): T[] {
    if (root === null) {
        return [];
    }
    
    const stack1: TreeNode<T>[] = [root];  // For traversal
    const stack2: TreeNode<T>[] = [];      // For reversing order
    
    // Phase 1: Modified preorder (Root → Right → Left) into stack2
    while (stack1.length > 0) {
        const current = stack1.pop()!;
        stack2.push(current);  // Push to stack2 (will reverse order)
        
        // Push LEFT first, then RIGHT
        // So RIGHT is on top and popped first → Root, Right, Left order
        if (current.left !== null) {
            stack1.push(current.left);
        }
        if (current.right !== null) {
            stack1.push(current.right);
        }
    }
    
    // Phase 2: Pop from stack2 to get postorder (reversed)
    const result: T[] = [];
    while (stack2.length > 0) {
        result.push(stack2.pop()!.value);
    }
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Trace for understanding
// ─────────────────────────────────────────────────────────────
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Phase 1 - Modified preorder into stack2:
 * 
 * stack1: [1]  → pop 1, push to stack2, then push 2 (left), 3 (right)
 * stack2: [1]
 * stack1: [2, 3]
 * 
 * stack1: [2, 3] → pop 3, push to stack2 (3 has no children)
 * stack2: [1, 3]
 * stack1: [2]
 * 
 * stack1: [2] → pop 2, push to stack2, then push 4, 5
 * stack2: [1, 3, 2]
 * stack1: [4, 5]
 * 
 * stack1: [4, 5] → pop 5, push to stack2
 * stack2: [1, 3, 2, 5]
 * stack1: [4]
 * 
 * stack1: [4] → pop 4, push to stack2
 * stack2: [1, 3, 2, 5, 4]
 * stack1: []
 * 
 * Phase 2 - Pop from stack2:
 * Pop order: 4, 5, 2, 3, 1  ← This is postorder! ✓
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

/**
 * Postorder traversal - iterative with ONE stack
 * 
 * Key Challenge: We need to know when we've finished both subtrees
 *                before we can visit a node.
 * 
 * Solution: Track the last visited node. If right child equals
 *           last visited, we've finished the right subtree.
 * 
 * Time Complexity:  O(n)
 * Space Complexity: O(h) - only one stack needed
 */
function postorderOneStack<T>(root: TreeNode<T> | null): T[] {
    const result: T[] = [];
    const stack: TreeNode<T>[] = [];
    let current: TreeNode<T> | null = root;
    let lastVisited: TreeNode<T> | null = null;
    
    while (current !== null || stack.length > 0) {
        // Phase 1: Go all the way left
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        // Peek at the top - don't pop yet!
        const top = stack[stack.length - 1];
        
        // Phase 2: Check if we can visit this node
        // We can visit if:
        //   (a) No right child exists, OR
        //   (b) Right child was just visited (we're returning from it)
        if (top.right === null || top.right === lastVisited) {
            // Safe to visit - both subtrees done
            result.push(top.value);
            lastVisited = stack.pop()!;
        } else {
            // Right subtree not processed yet - go right
            current = top.right;
        }
    }
    
    return result;
}
 
// ─────────────────────────────────────────────────────────────
// Alternative: Using a flag-based approach
// ─────────────────────────────────────────────────────────────
 
interface StackFrame<T> {
    node: TreeNode<T>;
    rightProcessed: boolean;
}
 
/**
 * One-stack with explicit "visited" flag per node
 * Conceptually clearer than tracking lastVisited
 */
function postorderWithFlag<T>(root: TreeNode<T> | null): T[] {
    if (root === null) {
        return [];
    }
    
    const result: T[] = [];
    const stack: StackFrame<T>[] = [{ node: root, rightProcessed: false }];
    
    while (stack.length > 0) {
        const frame = stack[stack.length - 1];
        
        if (frame.rightProcessed) {
            // Already processed right subtree - visit and pop
            result.push(frame.node.value);
            stack.pop();
        } else {
            // Mark right as processed (we're about to handle it)
            frame.rightProcessed = true;
            
            // Push right then left (so left is processed first)
            if (frame.node.right !== null) {
                stack.push({ node: frame.node.right, rightProcessed: false });
            }
            if (frame.node.left !== null) {
                stack.push({ node: frame.node.left, rightProcessed: false });
            }
        }
    }
    
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

INFORMATION FLOW IN TREE ALGORITHMS
═══════════════════════════════════════════════════════════════════════════
 
TOP-DOWN (Preorder-style):
──────────────────────────
Information flows from root → leaves
Parent provides info to children
 
Examples:
• Passing depth level to children
• Passing path constraints (like min/max for BST validation)
• Passing accumulated path values
 
Use preorder: process parent first, pass info to children
 
═══════════════════════════════════════════════════════════════════════════
 
BOTTOM-UP (Postorder-style):
────────────────────────────
Information flows from leaves → root
Children provide info to parent
 
Examples:
• Computing height (need children's heights first)
• Computing size (need children's sizes first)
• Deleting tree (need to delete children first)
• Evaluating expressions (need operands before applying operator)
 
Use postorder: process children first, then compute parent
 
═══════════════════════════════════════════════════════════════════════════
 
QUESTION TO ASK:
"Do I need to know something about my children to process myself?"
 
YES → Postorder (children first)
NO  → Preorder (self first) or Inorder (BST operations)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

/**
 * Delete all nodes in a tree using postorder traversal
 * 
 * Why postorder is REQUIRED:
 * 1. We must delete children before parent (dependency order)
 * 2. Deleting parent first would orphan children (memory leak in C/C++)
 * 3. Postorder naturally processes children before parent
 * 
 * In garbage-collected languages, this demonstrates proper cleanup
 * order for resources like file handles, connections, etc.
 */
function deleteTree<T>(root: TreeNode<T> | null): void {
    // Base case: nothing to delete
    if (root === null) {
        return;
    }
    
    // Postorder: process children BEFORE current node
    
    // Step 1: Delete left subtree first
    deleteTree(root.left);
    root.left = null;  // Clear reference
    
    // Step 2: Delete right subtree second
    deleteTree(root.right);
    root.right = null;  // Clear reference
    
    // Step 3: Now safe to "delete" current node
    // In languages with manual memory: free(root)
    // In JS/TS: Just let garbage collector handle it
    console.log(`Deleted node: ${root.value}`);
    
    // root will be garbage collected when no more references exist
}
 
/*
 * Tree:        1
 *             / \
 *            2   3
 *           / \
 *          4   5
 *
 * Deletion order (postorder): 4, 5, 2, 3, 1
 * 
 * Why this order is correct:
 * • Delete 4 (leaf, no children to worry about)
 * • Delete 5 (leaf, no children to worry about)
 * • Delete 2 (children 4,5 already deleted — safe!)
 * • Delete 3 (leaf, no children)
 * • Delete 1 (children 2,3 already deleted — safe!)
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

/**
 * Compute the height of a binary tree
 * 
 * Height definition: longest path from root to any leaf
 * (measured in edges, or equivalently, nodes - 1)
 * 
 * Why postorder:
 * - Height(node) = 1 + max(Height(left), Height(right))
 * - We NEED children's heights to compute parent's height
 * - Must compute children first → postorder!
 * 
 * Time Complexity: O(n) - visit each node once
 * Space Complexity: O(h) - recursion depth
 */
function treeHeight<T>(root: TreeNode<T> | null): number {
    // Base case: empty tree has height -1 (or 0 depending on definition)
    if (root === null) {
        return -1;  // Using edge-based definition
    }
    
    // Postorder: compute children's heights FIRST
    const leftHeight = treeHeight(root.left);    // LEFT
    const rightHeight = treeHeight(root.right);  // RIGHT
    
    // VISIT: Compute current node's height from children's heights
    const currentHeight = 1 + Math.max(leftHeight, rightHeight);
    
    return currentHeight;
}
 
/*
 * Tree:        1             Heights:      2
 *             / \                         / \
 *            2   3                        1   0
 *           / \                          / \
 *          4   5                         0   0
 *
 * Computation order (postorder):
 * • Height(4) = 1 + max(-1, -1) = 0
 * • Height(5) = 1 + max(-1, -1) = 0
 * • Height(2) = 1 + max(0, 0) = 1    ← needs 4,5 first!
 * • Height(3) = 1 + max(-1, -1) = 0
 * • Height(1) = 1 + max(1, 0) = 2    ← needs 2,3 first!
 */
 
// ─────────────────────────────────────────────────────────────
// More general pattern: any "combine children's results" problem
// ─────────────────────────────────────────────────────────────
 
/**
 * Generic postorder pattern for bottom-up computation
 */
function postorderCompute<T, R>(
    root: TreeNode<T> | null,
    baseCase: R,
    combine: (nodeValue: T, leftResult: R, rightResult: R) => R
): R {
    if (root === null) {
        return baseCase;
    }
    
    // Compute on children first (postorder)
    const leftResult = postorderCompute(root.left, baseCase, combine);
    const rightResult = postorderCompute(root.right, baseCase, combine);
    
    // Combine children's results with current node
    return combine(root.value, leftResult, rightResult);
}
 
// Height using the generic pattern:
const height = postorderCompute<number, number>(
    tree,
    -1,  // base case: empty tree height
    (value, leftH, rightH) => 1 + Math.max(leftH, rightH)
);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

interface ExprNode {
    value: string;
    left: ExprNode | null;
    right: ExprNode | null;
}
 
/**
 * Generate postfix notation from expression tree
 * Uses postorder: operands BEFORE operator
 */
function toPostfix(root: ExprNode | null): string {
    if (root === null) {
        return "";
    }
    
    // Leaf (operand)
    if (root.left === null && root.right === null) {
        return root.value;
    }
    
    // Postorder: left, right, then root (operator)
    const leftExpr = toPostfix(root.left);
    const rightExpr = toPostfix(root.right);
    
    return `${leftExpr} ${rightExpr} ${root.value}`;
}
 
/**
 * Evaluate a postfix expression using a stack
 * 
 * Algorithm:
 * - Scan left to right
 * - If operand: push to stack
 * - If operator: pop two operands, apply operator, push result
 * - Final stack value is the answer
 */
function evaluatePostfix(expression: string): number {
    const tokens = expression.split(" ");
    const stack: number[] = [];
    
    for (const token of tokens) {
        if (["+", "-", "*", "/"].includes(token)) {
            // Operator: pop two operands and compute
            const right = stack.pop()!;
            const left = stack.pop()!;
            
            let result: number;
            switch (token) {
                case "+": result = left + right; break;
                case "-": result = left - right; break;
                case "*": result = left * right; break;
                case "/": result = left / right; break;
                default: throw new Error(`Unknown operator: ${token}`);
            }
            
            stack.push(result);
        } else {
            // Operand: push to stack
            stack.push(parseFloat(token));
        }
    }
    
    return stack.pop()!;
}
 
// Example: (3 + 4) * (5 - 2)
const expressionTree: ExprNode = {
    value: "*",
    left: {
        value: "+",
        left: { value: "3", left: null, right: null },
        right: { value: "4", left: null, right: null },
    },
    right: {
        value: "-",
        left: { value: "5", left: null, right: null },
        right: { value: "2", left: null, right: null },
    },
};
 
const postfix = toPostfix(expressionTree);
console.log(postfix);  // "3 4 + 5 2 - *"
 
console.log(evaluatePostfix(postfix));  // 21
 
/*
 * Evaluation trace for "3 4 + 5 2 - *":
 * 
 * Token | Stack        | Action
 * ──────┼──────────────┼─────────────────────
 *   3   | [3]          | Push 3
 *   4   | [3, 4]       | Push 4
 *   +   | [7]          | Pop 4,3; push 3+4=7
 *   5   | [7, 5]       | Push 5
 *   2   | [7, 5, 2]    | Push 2
 *   -   | [7, 3]       | Pop 2,5; push 5-2=3
 *   *   | [21]         | Pop 3,7; push 7*3=21
 * 
 * Final answer: 21 ✓
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * Count total nodes in a tree
 * 
 * Size(node) = 1 + Size(left) + Size(right)
 * Must compute children's sizes first → postorder
 */
function countNodes<T>(root: TreeNode<T> | null): number {
    if (root === null) {
        return 0;
    }
    
    const leftCount = countNodes(root.left);
    const rightCount = countNodes(root.right);
    
    return 1 + leftCount + rightCount;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * Check if a binary tree is height-balanced
 * (Heights of left and right subtrees differ by at most 1 at every node)
 * 
 * Why postorder: Need heights of both subtrees to check balance
 * Optimization: Return -1 to indicate unbalanced (avoids separate boolean)
 */
function isBalanced<T>(root: TreeNode<T> | null): boolean {
    return checkHeight(root) !== -1;
}
 
function checkHeight<T>(root: TreeNode<T> | null): number {
    if (root === null) {
        return 0;
    }
    
    // Postorder: check children first
    const leftHeight = checkHeight(root.left);
    if (leftHeight === -1) return -1;  // Left subtree unbalanced
    
    const rightHeight = checkHeight(root.right);
    if (rightHeight === -1) return -1;  // Right subtree unbalanced
    
    // VISIT: Check current node's balance
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;  // This node is unbalanced
    }
    
    // Return height for parent's calculation
    return 1 + Math.max(leftHeight, rightHeight);
}
 
/*
 * The -1 sentinel pattern:
 * - Normally returns height (≥ 0)
 * - Returns -1 if any subtree is unbalanced
 * - Parent propagates -1 upward without additional checks
 * - Single O(n) pass instead of checking height at every node
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * Find the diameter of a binary tree
 * (Longest path between any two nodes, measured in edges)
 * 
 * Key insight: The longest path either:
 * 1. Goes through the current node (left height + right height + 2)
 * 2. Is entirely in left subtree
 * 3. Is entirely in right subtree
 * 
 * We need children's heights AND diameters → postorder
 */
function treeDiameter<T>(root: TreeNode<T> | null): number {
    let maxDiameter = 0;
    
    function height(node: TreeNode<T> | null): number {
        if (node === null) {
            return -1;
        }
        
        // Postorder: compute children's heights
        const leftH = height(node.left);
        const rightH = height(node.right);
        
        // VISIT: Update global max if path through this node is longest
        const diameterThroughNode = leftH + rightH + 2;
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
        
        return 1 + Math.max(leftH, rightH);
    }
    
    height(root);
    return maxDiameter;
}
 
/*
 * Tree:        1             Diameter = 4 (path: 4-2-1-3 or similar)
 *             / \
 *            2   3
 *           / \
 *          4   5
 *         /
 *        6
 *
 * At node 2: diameter through it = height(4)+height(5)+2 = 2+0+2 = 4
 */