Postorder Tree Traversal Tutorial | Learn Data Structures

What Is Postorder Traversal?

Postorder traversal is a depth-first tree traversal technique in which the left subtree and right subtree are processed before the current node.

Left → Right → Root

The name "postorder" describes the position of the current node. The node is processed after both of its child subtrees have been visited.

This traversal is particularly useful when a parent depends on work being completed for its children first. Common examples include deleting a tree, evaluating expression trees, calculating values from child nodes, and solving bottom-up tree problems.

Example Binary Tree

Consider the following binary tree:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

Postorder traversal first completes the left subtree, then the right subtree, and finally processes the root.

Postorder:

20 → 40 → 30 → 60 → 80 → 70 → 50

How Postorder Traversal Works

For every node, postorder traversal follows three steps:

Traverse the left subtree.
Traverse the right subtree.
Process the current node.

These steps are repeated recursively for every subtree until all nodes have been visited.

Tracing Postorder Traversal

Start with the root node 50. Postorder does not process it immediately because both of its subtrees must be completed first.

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

The traversal first enters the left subtree rooted at 30. Node 30 is also postponed while its children are processed.

Node 20 has no children, so it is processed first. Then node 40 is processed. Only after both children are complete is node 30 processed.

20 → 40 → 30

The same process happens in the right subtree. Nodes 60 and 80 are processed before node 70.

60 → 80 → 70

Once both subtrees of 50 have been completed, the root itself is processed last.

20 → 40 → 30 → 60 → 80 → 70 → 50

Recursive Postorder Traversal

Recursion provides a direct implementation of postorder traversal. The current node is added to the result only after both recursive calls have completed.

function postorder(root, result = []) {
  if (root === null) {
    return result;
  }

  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.value);

  return result;
}

The location of result.push(root.value) defines the traversal as postorder. Moving that statement before the recursive calls would produce a different traversal.

Complete Recursive Example

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function postorder(root, result = []) {
  if (root === null) {
    return result;
  }

  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.value);

  return result;
}

const root = new Node(50);

root.left = new Node(30);
root.right = new Node(70);

root.left.left = new Node(20);
root.left.right = new Node(40);

root.right.left = new Node(60);
root.right.right = new Node(80);

console.log(postorder(root));

Why Is the Root Processed Last?

Postorder traversal is designed for situations where the current node should only be handled after its descendants have been processed.

For example, if a parent node represents a container and its children represent resources inside that container, processing the children first allows the parent to be handled after everything below it has been completed.

Traversal	Order	Root Position
Preorder	Root → Left → Right	First
Inorder	Left → Root → Right	Middle
Postorder	Left → Right → Root	Last

Iterative Postorder Traversal Using Two Stacks

Postorder traversal is slightly more complicated to implement iteratively because a node must be processed only after both of its children.

One straightforward approach uses two stacks. The first stack controls traversal, while the second stack reverses the intermediate order so that the final result becomes Left-Right-Root.

function postorderIterative(root) {
  if (root === null) {
    return [];
  }

  const stack1 = [root];
  const stack2 = [];
  const result = [];

  while (stack1.length > 0) {
    const node = stack1.pop();

    stack2.push(node);

    if (node.left !== null) {
      stack1.push(node.left);
    }

    if (node.right !== null) {
      stack1.push(node.right);
    }
  }

  while (stack2.length > 0) {
    result.push(stack2.pop().value);
  }

  return result;
}

How the Two-Stack Approach Works

The first stack processes nodes in a root-right-left pattern and places them into the second stack. Popping the second stack reverses that order and produces the required left-right-root sequence.

First stack processing:
Root → Right → Left

Second stack reverses it:

Left → Right → Root

This approach is easy to understand and is useful when learning how iterative postorder traversal works.

Iterative Postorder Traversal Using One Stack

Postorder traversal can also be implemented using a single stack. The algorithm keeps track of the previously processed node so it can determine whether a node's right subtree has already been visited.

function postorderOneStack(root) {
  const stack = [];
  const result = [];
  let current = root;
  let previous = null;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    const node = stack[stack.length - 1];

    if (node.right !== null && previous !== node.right) {
      current = node.right;
    } else {
      result.push(node.value);
      previous = stack.pop();
    }
  }

  return result;
}

The algorithm moves left first. When the top node has a right subtree that has not yet been processed, traversal moves into that subtree. Otherwise, the node can safely be processed.

Postorder Traversal for Deleting a Tree

Postorder traversal is a natural fit for deleting or releasing nodes in a tree because children can be processed before their parent.

A postorder sequence is:

D → E → B → C → A

The descendants are therefore processed before the nodes that contain or reference them.

Postorder Traversal and Expression Trees

Postorder traversal has an important relationship with expression trees. When operators are stored at internal nodes and operands are stored at leaf nodes, postorder visits the operands before their operator.

Postorder traversal produces:

5 → 2 → 3 → * → +

This corresponds to the postfix expression:

5 2 3 * +

Postfix expressions are useful because operators appear after their operands, which allows them to be evaluated using a stack.

Postorder Traversal for Bottom-Up Processing

Many tree algorithms need information from child nodes before the parent can be processed. Postorder traversal naturally provides this bottom-up processing order.

For example, a tree algorithm can calculate the height of each child first and then use those values to calculate the height of its parent.

function height(root) {
  if (root === null) {
    return 0;
  }

  const leftHeight = height(root.left);
  const rightHeight = height(root.right);

  return 1 + Math.max(leftHeight, rightHeight);
}

Although the function does not explicitly build a traversal array, its recursive computation follows the same bottom-up principle as postorder traversal.

Postorder Traversal in Binary Search Trees

Postorder traversal can be applied to a Binary Search Tree just like any other binary tree. However, unlike inorder traversal, it does not produce values in sorted order.

BST:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Postorder:

20, 40, 30, 60, 80, 70, 50

The useful property here is that each node appears after its descendants, rather than producing a sorted sequence.

Postorder Traversal Complexity

A complete postorder traversal visits every node exactly once. Therefore, the time complexity is O(n), where n is the number of nodes.

Implementation	Time	Auxiliary Space
Recursive	O(n)	O(h)
Two stacks	O(n)	O(n)
One stack	O(n)	O(h)

Here, h represents the height of the tree. A balanced tree typically has height O(log n), while a highly skewed tree can have height O(n).

When Should You Use Postorder Traversal?

Postorder is a useful choice whenever a node should be processed after the work associated with its descendants has been completed.

Deleting or releasing nodes from a tree
Evaluating expression trees
Generating postfix expressions
Calculating values from child nodes
Bottom-up tree algorithms
Computing tree height and similar properties
Solving binary tree coding and interview problems

Common Postorder Traversal Mistakes

Processing the current node before its children.
Confusing postorder with inorder traversal.
Forgetting that the right subtree must be processed before the root.
Missing the null-node base case in recursive implementations.
Using an incorrect stack order in iterative implementations.
Assuming postorder traversal produces sorted values from a BST.
Forgetting to track whether the right subtree has already been visited in a one-stack solution.

Postorder vs Inorder vs Preorder

All three are depth-first traversals. The main difference is the position at which the current node is processed.

Traversal	Pattern	Root Position	Common Use
Preorder	Root → Left → Right	First	Parent-before-child processing
Inorder	Left → Root → Right	Middle	Sorted BST output
Postorder	Left → Right → Root	Last	Bottom-up processing

Key Takeaways

Postorder traversal follows Left → Right → Root.
The current node is processed only after both child subtrees.
Postorder is a depth-first traversal technique.
Recursive implementation naturally follows the traversal definition.
Iterative implementations can use one or two stacks.
Two-stack postorder is straightforward to understand, while one-stack traversal uses less auxiliary space.
Postorder is useful for bottom-up tree processing.
It is commonly associated with postfix expression generation.
Postorder traversal of a BST does not produce sorted values.
A complete postorder traversal takes O(n) time.

Topics

Postorder Tree Traversal