Tree Traversal

Post-order

What is Post-order Traversal?

Post-order traversal visits both of a node's subtrees before the node itself — the order is Left, Right, Root. It's called "post" because the root is processed after everything below it has already been dealt with, the exact opposite of pre-order.

How Does It Work?

  1. Start at the root (8), but don't visit it yet — first fully process the left subtree
  2. At 3, also hold off — go left first: reach 1 (a leaf) — visit it: 1
  3. Back at 3, go right: reach 6 (a leaf) — visit it: 1, 6
  4. Both of 3's children are done — now visit 3: 1, 6, 3
  5. Back at 8, its left subtree is fully done — go right: reach 10 — visit it: 1, 6, 3, 10
  6. Both of 8's subtrees are done — finally visit 8 (the root, last): 1, 6, 3, 10, 8
85331162104
Visit orderNode

That "children before parent" ordering makes post-order the natural choice whenever you need to fully finish with a node's descendants before touching the node itself. The two classic examples are deleting or freeing a tree's memory (you must free the children before the parent, otherwise you'd lose your only reference to them) and evaluating an expression tree (you can't compute an operator's result until both of its operand subtrees have already been evaluated).

Post-order also mirrors how you'd write a postfix (Reverse Polish) expression from an expression tree: the operands come first and the operator comes last, e.g. `3 4 +` instead of `3 + 4`.

Algorithm Steps

  1. If the current node is null, return immediately (base case)
  2. Recursively traverse the left subtree
  3. Recursively traverse the right subtree
  4. Visit (process) the current node last

Time Complexity

  • Time Complexity: Every node is visited exactly once → O(n).
  • Space Complexity: Bounded by the recursion depth → O(h).

Time Complexity Analysis

Advertisement

Traversal needs O(h) extra space for the recursion call stack, where h is the tree's height — O(log n) for a balanced tree, but O(n) in the worst case of a completely skewed tree.

Daily DSA Challenge by Scale Engineer

Build a tree, then watch post-order visit Left → Right → Root

Tree is empty
No tree yet — insert a value or generate a random tree
Not yet visitedVisitedCurrently visitingRoot

Test Your Knowledge before moving forward!

Post-order Traversal Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Post-order Traversal Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Post-order traversal: Left -> Right -> Root
function postOrder(node, result = []) {
  if (node === null) return result;

  postOrder(node.left, result);
  postOrder(node.right, result);
  result.push(node.value); // visit root last

  return result;
}

// Usage example
let root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);

console.log(postOrder(root)); // [1, 6, 3, 10, 8]

Done With the Learning

Mark Post-order Traversal as done and view it on your dashboard

Explore Other Tree Topics

Pre-order Traversal

In-order Traversal

Level-order Traversal

Morris Traversal

BST Insertion

BST Deletion

AVL Balancing