Postorder Traversal of a Binary Tree - Recursion - Visualization

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, perform a postorder traversal using recursion. In a postorder traversal, the nodes are visited in the order: left subtree, right subtree, then the current node. You need to return a list containing the values of the nodes in postorder.

Examples❯

Input Tree Postorder Output Description
[1, null, 2, null, null, null, 3]
[3, 2, 1] Right-skewed tree with nodes processed left to right and then root.
[1, 2, 3]
[2, 3, 1] Balanced tree with left and right children.
[1]
[1] Single node tree, output is just the root.
[] [] Empty tree, no nodes to process.
[1, 2, null, 3]
[3, 2, 1] Left-skewed tree with nodes deeply nested on left.

Solution❯

Understanding the Problem

In this problem, we are asked to perform a postorder traversal on a binary tree using recursion. Postorder traversal is one of the depth-first traversal techniques in binary trees, and it follows a specific order:

  • Traverse the left subtree
  • Traverse the right subtree
  • Visit the root node

In other words, for each node, we visit all its children before we visit the node itself. This order is especially useful when you want to delete or evaluate trees from the bottom-up.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let’s take a sample binary tree:


      1
     /     2   3

Here, the root is 1, the left child is 2, and the right child is 3.

Step 2: Apply Postorder Traversal Definition

We follow the left → right → root order. So we:

  • First traverse the left subtree rooted at 2
  • Then traverse the right subtree rooted at 3
  • Then visit the root node, which is 1

This gives the output: [2, 3, 1]

Step 3: Write the Recursive Code


function postorderTraversal(root) {
  if (root === null) return [];
  const left = postorderTraversal(root.left);
  const right = postorderTraversal(root.right);
  return [...left, ...right, root.val];
}

This code breaks down the problem into smaller subproblems, solving the postorder traversal for each subtree and then combining the results.

Step 4: Recap the Recursive Flow

For a node, we call the function recursively on the left child, then the right child, and finally add the current node's value to the result list. This ensures all children are processed before the parent node, just like postorder requires.

Edge Cases

Case 1: Empty Tree

If the tree is empty (null), the output should be an empty array []. The function handles this gracefully with the base case check.

Case 2: Single Node Tree

For a tree with only one node (e.g., [1]), the traversal returns just [1] since there are no children.

Case 3: Left-skewed Tree

Consider a tree like [1, 2, null, 3]. It looks like:


    1
   /
  2
 /
3

We go left down to 3, then back up: [3, 2, 1]

Case 4: Right-skewed Tree

For [1, null, 2, null, 3]:


1
   2
       3

The output will be [3, 2, 1]

Case 5: Balanced Tree

Our initial example [1, 2, 3] is a good case of a balanced tree, resulting in [2, 3, 1].

Finally

Postorder traversal is a fundamental recursive algorithm for binary trees. It emphasizes processing children before parents, and it’s useful in many scenarios like expression tree evaluation, directory cleanup, and more.

By breaking the problem down recursively and understanding the order clearly, even beginners can master this traversal. Always consider edge cases like empty trees or skewed trees while designing and testing your solution.

Algorithm Steps❯

  1. Start at the root of the binary tree.
  2. Recursively traverse the left subtree.
  3. Recursively traverse the right subtree.
  4. Visit (process) the current node.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *left, *right;
} Node;

Node* newNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->value);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    postorder(root);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...