Tree Traversal Postorder Left Right Root in DSA Typescript

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: 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) to node 2

Visiting node 2 -> left child 4 and right child 5

Why: We must visit left subtree before root

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

At node 4 with no children

Why: Left subtree of 2 is 4, visit it first

Step 3: Visit node 4 (leaf), print 4

Output so far: 4

Why: No children, so print node

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

At node 5 with no children

Why: After left subtree, visit right subtree

Step 5: Visit node 5 (leaf), print 5

Output so far: 4 5

Why: No children, so print node

Step 6: Visit node 2 (after left and right subtrees), print 2

Output so far: 4 5 2

Why: Root printed after children

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

At node 3 with no children

Why: After left subtree, visit right subtree

Step 8: Visit node 3 (leaf), print 3

Output so far: 4 5 2 3

Why: No children, so print node

Step 9: Visit root node 1 (after left and right subtrees), print 1

Output so far: 4 5 2 3 1

Why: Root printed last

Result:

4 5 2 3 1

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function postorderTraversal(root: TreeNode | null, result: number[] = []): number[] {
  if (root === null) return result; // base case: empty node
  postorderTraversal(root.left, result); // traverse left subtree
  postorderTraversal(root.right, result); // traverse right subtree
  result.push(root.val); // visit root last
  return result;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);
const output = postorderTraversal(root);
console.log(output.join(' '));

if (root === null) return result;

stop recursion at empty node

postorderTraversal(root.left, result);

traverse left subtree first

postorderTraversal(root.right, result);

then traverse right subtree

result.push(root.val);

visit root node last

Output

4 5 2 3 1

Complexity Analysis

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

Space: O(n) due to recursion stack in worst case and output storage

vs Alternative: Compared to preorder or inorder, postorder also visits all nodes once, so time is same; space depends on tree height

Edge Cases

Empty tree (root is null)

Returns empty list without error

DSA Typescript

if (root === null) return result;

Single node tree

Returns list with single node value

DSA Typescript

result.push(root.val);

Tree with only left children

Traverses down left side and prints nodes bottom-up

DSA Typescript

postorderTraversal(root.left, result);

When to Use This Pattern

When you need to process children before the parent, especially for deleting or evaluating expressions, use postorder traversal.

Common Mistakes

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

Mistake: Forgetting to check for null nodes causing errors
Fix: Add base case to return when node is null

Summary

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

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

The root is visited only after all its children have been visited.