Tree Traversal Postorder Left Right Root in DSA Javascript

Mental Model

Visit the left side first, then the right side, and finally the root node last.

Analogy: Imagine cleaning a room by first tidying the left corner, then the right corner, and only after both are clean, you clean the center of the room.

    1
   / \
  2   3
 / \
4   5
↑ root

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Traverse left subtree of root (1), move to node 2

    1
   / \
  [2] 3
 / \
4   5
↑ current at 2

Why: We must visit left subtree before root

Step 2: Traverse left subtree of node 2, move to node 4

    1
   / \
  2   3
 / \
[4]  5
↑ current at 4

Why: Left subtree of 2 must be visited first

Step 3: Node 4 has no children, print 4 and return to node 2

4 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 2

Why: Leaf node visited, now visit right subtree

Step 4: Traverse right subtree of node 2, move to node 5

    1
   / \
  2   3
 / \
4  [5]
↑ current at 5

Why: Right subtree of 2 must be visited after left

Step 5: Node 5 has no children, print 5 and return to node 2

5 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 2

Why: Leaf node visited, now print node 2

Step 6: Print node 2 and return to root 1

2 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 1

Why: Both subtrees of 2 visited, now print 2

Step 7: Traverse right subtree of root (1), move to node 3

    1
   / \
  2  [3]
 / \
4   5
↑ current at 3

Why: Right subtree of root must be visited after left

Step 8: Node 3 has no children, print 3 and return to root 1

3 printed
    1
   / \
  2   3
 / \
4   5
↑ back at 1

Why: Leaf node visited, now print root

Step 9: Print root node 1

1 printed
    1
   / \
  2   3
 / \
4   5
Traversal complete

Why: All subtrees visited, print root last

Result:

4 -> 5 -> 2 -> 3 -> 1 -> null

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function postorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node === null) return;
    traverse(node.left); // visit left subtree
    traverse(node.right); // visit right subtree
    result.push(node.val); // visit root last
  }
  traverse(root);
  return result;
}

// Build tree from dry_run input
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const output = postorderTraversal(root);
console.log(output.join(' -> ') + ' -> null');

if (node === null) return;

stop traversal when no node to visit

traverse(node.left); // visit left subtree

advance to left child first

traverse(node.right); // visit right subtree

then advance to right child

result.push(node.val); // visit root last

add current node value after children visited

Output

4 -> 5 -> 2 -> 3 -> 1 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) due to recursion stack and result storage for all nodes

vs Alternative: Compared to iterative traversal, recursive is simpler but uses call stack; iterative may use explicit stack but same O(n) time

Edge Cases

Empty tree (root is null)

Returns empty list without error

DSA Javascript

if (node === null) return;

Single node tree

Returns list with single node value

DSA Javascript

if (node === null) return;

Tree with only left children

Visits all left nodes before root

DSA Javascript

traverse(node.left);

When to Use This Pattern

When you need to process children before the parent, especially for deleting or evaluating expressions, use postorder traversal because it ensures children are handled first.

Common Mistakes

Mistake: Visiting root before children (preorder) instead of after
Fix: Move the root visit (push) after traversing left and right children

Mistake: Forgetting to check for null node before recursion
Fix: Add base case 'if (node === null) return;' to stop recursion

Summary

Visits left subtree, then right subtree, then the root node last.

Use when you want to process children before their parent, like in expression evaluation or tree deletion.

The key is to delay visiting the root until both subtrees are fully processed.