What does postorder traversal (postfix tree traversal) do?

AlgorithmsJunior~2 min read

Short answer

Postorder traversal (postfix traversal) is a depth-first tree traversal that visits nodes in the order: left subtree, right subtree, the node itself (L-R-Root). For an n-ary tree: all children left to right, then the node.

Detailed explanation

Postorder traversal is one form of depth-first search (DFS). The main idea: fully process the subtrees first, then the current node. This makes postorder a natural choice for problems where a node's value depends on the results from its descendants.

Traversal order (binary tree): left subtree, right subtree, node (L-R-Root).
For an n-ary tree: traverse all children left to right, then the current node.
Complexity: time O(n), memory O(h) with recursion (h is the tree's height). Iterative versions use O(h) extra memory for the stack.
Where it's useful: evaluating expression trees (producing postfix form), deleting/freeing a tree bottom-up, computing subtree sizes/heights, serialization in reverse Polish notation.

Example on a tree

      A
     / \
    B   C
   / \
  D   E

Postorder: D, E, B, C, A

Recursive implementation (JavaScript)

// Binary tree node
// { val: any, left: Node|null, right: Node|null }

function postorderRecursive(node, visit) {
  if (!node) return;
  postorderRecursive(node.left, visit);
  postorderRecursive(node.right, visit);
  visit(node);
}

// Example
const tree = {
  val: 'A',
  left: {
    val: 'B',
    left: { val: 'D', left: null, right: null },
    right: { val: 'E', left: null, right: null }
  },
  right: { val: 'C', left: null, right: null }
};

const result = [];
postorderRecursive(tree, n => result.push(n.val));
console.log(result); // ['D', 'E', 'B', 'C', 'A']

Iterative implementation (JavaScript, no recursion)

A single-stack approach with a pointer to the last visited node. We move left, then check the right child and decide whether to descend or visit the top of the stack.

function postorderIterative(root, visit) {
  const stack = [];
  let lastVisited = null;
  let curr = root;

  while (stack.length || curr) {
    if (curr) {
      stack.push(curr);
      curr = curr.left;
    } else {
      const peek = stack[stack.length - 1];
      if (peek.right && lastVisited !== peek.right) {
        curr = peek.right;
      } else {
        visit(peek);
        lastVisited = stack.pop();
      }
    }
  }
}

// Check
const out = [];
postorderIterative(tree, n => out.push(n.val));
console.log(out); // ['D', 'E', 'B', 'C', 'A']

N-ary tree

In an n-ary tree, a node has a children array. We traverse all children left to right, then visit the current node:

// N-ary tree node: { val, children: Node[] }
function postorderNAry(node, visit) {
  if (!node) return;
  for (const child of node.children || []) {
    postorderNAry(child, visit);
  }
  visit(node);
}

// Example structure:
const nary = {
  val: 'A',
  children: [
    { val: 'B', children: [ { val: 'E', children: [] }, { val: 'F', children: [] } ] },
    { val: 'C', children: [] },
    { val: 'D', children: [] }
  ]
};

const order = [];
postorderNAry(nary, n => order.push(n.val));
console.log(order); // ['E', 'F', 'B', 'C', 'D', 'A']

Common tasks that need postorder traversal

Expression trees: evaluating a value and generating reverse Polish notation.
Deleting/freeing a tree: free the descendants first, then the parent.
Counting subtree properties: sizes, heights, sums of values.
Serialization/copying, when a bottom-up order is critical.

Edge cases and notes

Empty tree: the traversal does nothing.
Single node: the root itself is returned.
Heavily unbalanced tree: recursion depth can reach O(n); use the iterative variant if stack overflow is a risk.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.