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:

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:

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)

to clipboard
Copy to clipboard

Output generated by this code will be:

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

to clipboard
Copy to clipboard

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)

to clipboard
Copy to clipboard

The output of this code will be:

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

to clipboard
Copy to clipboard

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")

to clipboard
Copy to clipboard

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