Postorder Traversal of a Binary Tree Using Recursion

Problem and examples

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.

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.

Explore Postorder Traversal of a Binary Tree - Recursion

Load an example or enter your own input. Use the player controls to follow each change.

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:

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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *left, *right;
    Node(int val) : value(val), left(nullptr), right(nullptr) {}
};

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->value << " ";
}

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

Python implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def postorder(root):
    if root is not None:
        postorder(root.left)
        postorder(root.right)
        print(root.value, end=' ')

# Example usage:
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    postorder(root)

Java implementation

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

public class PostorderTraversal {
    public static void postorder(Node root) {
        if (root == null) return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.value + " ");
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        postorder(root);
    }
}

JavaScript implementation

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

function postorder(root) {
    if (root === null) return;
    postorder(root.left);
    postorder(root.right);
    console.log(root.value);
}

// Example usage:
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
postorder(root);

Go implementation

package main

import "fmt"

type Node struct {
    value int
    left  *Node
    right *Node
}

func newNode(value int) *Node {
    return &Node{value: value}
}

func postorder(root *Node) {
    if root == nil {
        return
    }
    postorder(root.left)
    postorder(root.right)
    fmt.Printf("%d ", root.value)
}

func main() {
    root := newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    postorder(root)
}

Rust implementation

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(value: i32) -> Self {
        Node { value, left: None, right: None }
    }
}

fn postorder(node: &Option<Box<Node>>) {
    if let Some(n) = node {
        postorder(&n.left);
        postorder(&n.right);
        print!("{} ", n.value);
    }
}

fn main() {
    let mut root = Box::new(Node::new(1));
    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(3)));
    root.left.as_mut().unwrap().left = Some(Box::new(Node::new(4)));
    root.left.as_mut().unwrap().right = Some(Box::new(Node::new(5)));
    postorder(&Some(root));
}

Kotlin implementation

class Node(val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

fun postorder(root: Node?) {
    if (root == null) return
    postorder(root.left)
    postorder(root.right)
    print("${root.value} ")
}

fun main() {
    val root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left!!.left = Node(4)
    root.left!!.right = Node(5)
    postorder(root)
}

Swift implementation

class Node {
    var value: Int
    var left: Node?
    var right: Node?

    init(_ value: Int) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

func postorder(_ root: Node?) {
    guard let root = root else { return }
    postorder(root.left)
    postorder(root.right)
    print("\(root.value)", terminator: " ")
}

let root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left?.left = Node(4)
root.left?.right = Node(5)
postorder(root)

TypeScript implementation

class Node {
    value: number;
    left: Node | null;
    right: Node | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function postorder(root: Node | null): void {
    if (!root) return;
    postorder(root.left);
    postorder(root.right);
    console.log(root.value);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
postorder(root);