Postorder Traversal

MamtaWardhani's avatar
Published Aug 10, 2022Updated Apr 30, 2025
Contribute to Docs

Postorder traversal is a depth-first tree traversal algorithm where each node is visited in a specific sequence: left subtree, right subtree, and finally the root node. This traversal technique recursively processes all children of a node before processing the node itself, making it especially useful for operations that require bottom-up processing.

Postorder traversal has several important applications in computer science and data processing. It’s commonly used for deleting trees (since children must be deleted before their parent nodes), evaluating postfix expressions, and calculating directory sizes in file systems. When applied to expression trees, postorder traversal naturally produces postfix notation, which is valuable in compiler design and expression evaluation.

Algorithm

To perform a postorder traversal of a binary tree:

  1. Recursively traverse the left subtree
  2. Recursively traverse the right subtree
  3. Visit the root node

For a general tree (where nodes can have more than two children):

  1. Recursively traverse all children from left to right
  2. Visit the root node

Post order traversal returns a sequence of node values that represents the order in which nodes were visited. For the following binary search tree:

Binary Search Tree Diagram

Postorder traversal provides the nodes in the following order: 1, 3, 2, 5, 7, 6, 4.

Example 1: Basic Post Order Traversal Using Python

This example demonstrates how to implement a simple post order traversal of a binary tree using recursion in Python:

class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def post_order_traversal(root):
"""
Performs a post order traversal of a binary tree.
Args:
root: The root node of the binary tree
Returns:
A list containing node values in post order
"""
result = []
# Helper function for recursion
def traverse(node):
# Base case: if node is None, return
if node is None:
return
# First, visit left subtree
traverse(node.left)
# Then, visit right subtree
traverse(node.right)
# Finally, visit the node itself (add to result)
result.append(node.value)
# Start traversal from root
traverse(root)
return result
# Example usage
if __name__ == "__main__":
# Create a simple binary tree
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Perform post order traversal
result = post_order_traversal(root)
print("Post order traversal:", result)

Output generated by this code will be:

Post order traversal: [4, 5, 2, 3, 1]

In this example, we traverse the tree in postorder: left subtree (4, 5, 2), then right subtree (3), and finally the root (1). The output demonstrates that postorder traversal visits children before their parent nodes.

Example 2: Iterative Post Order Traversal Using Python

This example shows how to implement postorder traversal without recursion, using an iterative approach with two stacks in Python:

class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def iterative_post_order(root):
"""
Performs a post order traversal of a binary tree iteratively using two stacks.
Args:
root: The root node of the binary tree
Returns:
A list containing node values in post order
"""
if not root:
return []
result = []
stack1 = [root] # First stack for traversal
stack2 = [] # Second stack to store post order
# Process all nodes
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
node = stack2.pop()
result.append(node.value)
return result
# Example usage
if __name__ == "__main__":
# Create a binary tree
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
result = iterative_post_order(root)
print("Iterative post order traversal:", result)

The output of this code will be:

Iterative post order traversal: [4, 5, 2, 6, 3, 1]

This example demonstrates an alternative non-recursive approach to postorder traversal. The iterative solution is particularly useful when dealing with deep trees where recursive approaches might cause stack overflow issues.

Codebyte Example: Calculating Directory Size Using Python

This example demonstrates a practical application of postorder traversal for calculating the total size of directories in a file system using Python:

class FileNode:
def __init__(self, name, is_directory=False, size=0):
self.name = name
self.is_directory = is_directory
self.size = size # Size in bytes (only for files)
self.children = [] # For directories, list of files/subdirectories
def calculate_directory_sizes(root):
"""
Calculate sizes of all directories using post order traversal.
Args:
root: Root directory node
Returns:
Dictionary mapping directory names to their total sizes
"""
directory_sizes = {}
def traverse(node):
# Base case: if it's a file, return its size
if not node.is_directory:
return node.size
# For directories, calculate total size from children
total_size = 0
# Visit all children first (post order)
for child in node.children:
total_size += traverse(child)
# Store the directory's total size
directory_sizes[node.name] = total_size
return total_size
# Start traversal from root directory
traverse(root)
return directory_sizes
# Example usage
if __name__ == "__main__":
# Create a sample file system structure
# root (dir)
# / \
# docs (dir) images (dir)
# / \ / \
# f1.txt f2.txt img1.jpg img2.jpg
root = FileNode("root", is_directory=True)
docs = FileNode("docs", is_directory=True)
f1 = FileNode("f1.txt", size=100) # 100 bytes
f2 = FileNode("f2.txt", size=200) # 200 bytes
docs.children = [f1, f2]
images = FileNode("images", is_directory=True)
img1 = FileNode("img1.jpg", size=500) # 500 bytes
img2 = FileNode("img2.jpg", size=700) # 700 bytes
images.children = [img1, img2]
root.children = [docs, images]
# Calculate directory sizes
sizes = calculate_directory_sizes(root)
# Display results
for directory, size in sizes.items():
print(f"{directory}: {size} bytes")

This example illustrates how postorder traversal naturally solves the problem of calculating directory sizes. Since knowledge of the sizes of all subdirectories is needed before calculating the size of a parent directory, postorder traversal ensures processing of children occurs before processing of parents.

Frequently Asked Questions

1. What is the difference between preorder, in-order, and postorder traversal?

  • Preorder: Visit root, then left subtree, then right subtree (Root → Left → Right)
  • Inorder: Visit left subtree, then root, then right subtree (Left → Root → Right)
  • Postorder: Visit left subtree, then right subtree, then root (Left → Right → Root)

2. What is the time complexity of postorder traversal?

The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited exactly once.

3. What is the space complexity of postorder traversal?

  • For recursive implementation: O(h) where h is the height of the tree (due to the recursion stack)
  • For iterative implementation with stacks: O(n) in the worst case

4. When should I use postorder traversal instead of other traversal methods?

  • Use postorder traversal when you need to process child nodes before their parent nodes
  • Common applications include tree deletion, evaluating postfix expressions, and bottom-up computations

5. Can postorder traversal be used for non-binary trees?

Yes, postorder traversal can be generalized to n-ary trees by visiting all children before the parent node

All contributors

Contribute to Docs

Learn more on Codecademy