Suggest an edit

Improve this article

Refine the answer for “What does postorder traversal (postfix tree traversal) do?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts576 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.