DSA Post-order Traversal

Welcome to TheCodingCollege.com! In this guide, we’ll explore Post-order Traversal in Data Structures and Algorithms (DSA). This traversal is particularly useful in applications like evaluating expression trees and deleting nodes from a tree.

What is Post-order Traversal?

Post-order traversal is a method of visiting all nodes in a binary tree. The sequence is:

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

Key Characteristics of Post-order Traversal

  • It is a depth-first search (DFS) technique.
  • Post-order traversal is used for operations that require processing child nodes before their parent node.
  • It generates postfix expressions in expression trees.

Post-order Traversal Algorithm

Recursive Approach

  1. Start from the root node.
  2. Recursively traverse the left subtree.
  3. Recursively traverse the right subtree.
  4. Process the root node.

Iterative Approach

  1. Use two stacks (or one stack with a marker) to emulate the recursive behavior.
  2. Push nodes onto the stack while exploring left and right subtrees.
  3. Process nodes in reverse order to achieve post-order traversal.

Post-order Traversal Implementation

Recursive Implementation in Python

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

def postorder_recursive(node):
    if node:
        postorder_recursive(node.left)  # Traverse left subtree
        postorder_recursive(node.right)  # Traverse right subtree
        print(node.value, end=" ")  # Visit the root

# Example Usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

postorder_recursive(root)  # Output: 4 5 2 3 1

Iterative Implementation in Python

def postorder_iterative(root):
    if not root:
        return
    stack1 = [root]
    stack2 = []
    while stack1:
        current = stack1.pop()
        stack2.append(current)
        if current.left:
            stack1.append(current.left)
        if current.right:
            stack1.append(current.right)
    while stack2:
        print(stack2.pop().value, end=" ")  # Process nodes in reverse order

# Example Usage
postorder_iterative(root)  # Output: 4 5 2 3 1

Post-order Traversal Example

Consider the binary tree:

        1
       / \
      2   3
     / \
    4   5
  • Post-order Traversal: 4 → 5 → 2 → 3 → 1

Applications of Post-order Traversal

  1. Expression Trees:
    Post-order traversal is used to evaluate postfix expressions.
  2. Tree Deletion:
    It ensures child nodes are deleted before their parent node.
  3. Complex Tree Operations:
    Suitable for operations requiring processing of child nodes first, such as calculating tree depth.

Time and Space Complexity

AspectRecursive ApproachIterative Approach
Time ComplexityO(n)O(n)
Space ComplexityO(h) (call stack)O(2h) (two stacks)
  • n: Number of nodes in the tree.
  • h: Height of the tree.

Common Post-order Traversal Questions

  1. Evaluate an expression tree using post-order traversal.
  2. Implement post-order traversal to delete all nodes in a binary tree.
  3. Count the number of leaf nodes in a binary tree using post-order traversal.

Practice Problem

Given the binary tree:

        10
       /  \
      20   30
     / \    
    40  50

Write the post-order traversal of this tree.

Solution: 40 → 50 → 20 → 30 → 10

Conclusion

Post-order traversal is essential for solving tree-based problems in DSA. Understanding its recursive and iterative approaches will strengthen your skills in handling binary tree problems.

Leave a Comment