Postorder Traversal
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:
- Recursively traverse the left subtree
- Recursively traverse the right subtree
- Visit the root node
For a general tree (where nodes can have more than two children):
- Recursively traverse all children from left to right
- 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:
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 = valueself.left = Noneself.right = Nonedef post_order_traversal(root):"""Performs a post order traversal of a binary tree.Args:root: The root node of the binary treeReturns:A list containing node values in post order"""result = []# Helper function for recursiondef traverse(node):# Base case: if node is None, returnif node is None:return# First, visit left subtreetraverse(node.left)# Then, visit right subtreetraverse(node.right)# Finally, visit the node itself (add to result)result.append(node.value)# Start traversal from roottraverse(root)return result# Example usageif __name__ == "__main__":# Create a simple binary tree# 1# / \# 2 3# / \# 4 5root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)# Perform post order traversalresult = 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 = valueself.left = Noneself.right = Nonedef 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 treeReturns:A list containing node values in post order"""if not root:return []result = []stack1 = [root] # First stack for traversalstack2 = [] # Second stack to store post order# Process all nodeswhile 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 usageif __name__ == "__main__":# Create a binary tree# 1# / \# 2 3# / \ \# 4 5 6root = 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 = nameself.is_directory = is_directoryself.size = size # Size in bytes (only for files)self.children = [] # For directories, list of files/subdirectoriesdef calculate_directory_sizes(root):"""Calculate sizes of all directories using post order traversal.Args:root: Root directory nodeReturns:Dictionary mapping directory names to their total sizes"""directory_sizes = {}def traverse(node):# Base case: if it's a file, return its sizeif not node.is_directory:return node.size# For directories, calculate total size from childrentotal_size = 0# Visit all children first (post order)for child in node.children:total_size += traverse(child)# Store the directory's total sizedirectory_sizes[node.name] = total_sizereturn total_size# Start traversal from root directorytraverse(root)return directory_sizes# Example usageif __name__ == "__main__":# Create a sample file system structure# root (dir)# / \# docs (dir) images (dir)# / \ / \# f1.txt f2.txt img1.jpg img2.jpgroot = FileNode("root", is_directory=True)docs = FileNode("docs", is_directory=True)f1 = FileNode("f1.txt", size=100) # 100 bytesf2 = FileNode("f2.txt", size=200) # 200 bytesdocs.children = [f1, f2]images = FileNode("images", is_directory=True)img1 = FileNode("img1.jpg", size=500) # 500 bytesimg2 = FileNode("img2.jpg", size=700) # 700 bytesimages.children = [img1, img2]root.children = [docs, images]# Calculate directory sizessizes = calculate_directory_sizes(root)# Display resultsfor 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
Contribute to Docs
- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.
Learn more on Codecademy
- Career path
Computer Science
Looking for an introduction to the theory behind programming? Master Python while learning data structures, algorithms, and more!Includes 6 CoursesWith Professional CertificationBeginner Friendly75 hours - Course
Learn Python 3
Learn the basics of Python 3.12, one of the most powerful, versatile, and in-demand programming languages today.With CertificateBeginner Friendly23 hours