Postorder Traversal of a Binary Tree Using Recursion - Algorithm, Visualization, Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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.

Visualization Player

Solution❯

Case 1: Normal Tree with Left and Right Children

In a balanced or full binary tree where each node has both left and right children, postorder traversal means visiting all nodes in the left subtree first, then all nodes in the right subtree, and finally the root. For example, in the tree [1, 2, 3], we first visit 2 (left), then 3 (right), and finally 1 (root). This results in the output [2, 3, 1].

Case 2: Right-skewed Tree

In a right-skewed tree like [1, null, 2, 3], the traversal starts from the rightmost node. We go as deep as possible to the right, visiting 3 first (right child of 2), then 2, and finally 1. So, the postorder becomes [3, 2, 1].

Case 3: Left-skewed Tree

For a left-skewed tree such as [1, 2, null, 3], the traversal first processes the deepest left node, which is 3. Then we go up and process 2, and finally 1. This order results in [3, 2, 1].

Case 4: Single Node Tree

In the simplest case where the tree contains only one node (e.g., [1]), there are no children to process. So, the output is simply the root node: [1].

Case 5: Empty Tree

If the tree is empty (represented as []), there are no nodes to process. The result is just an empty list []. This case is important to handle gracefully without errors in recursive code.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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)