💡 Problem Formulation: Postorder traversal of a binary tree involves visiting a tree’s nodes in a specific order: first the left subtree, then the right subtree, and finally the root node. This task is crucial in various applications such as expression tree evaluations and file system hierarchy processing. Given a binary tree, we want to print or return a list of its nodes in postorder sequence.
Method 1: Recursive Traversal
This method employs the classic recursive approach where the function calls itself to traverse the left subtree, then the right subtree, and finally processes the root. It is intuitive and mirrors the definition of postorder traversal.
Here’s an example:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def postorderTraversal(root):
def recur(node, result):
if node:
recur(node.left, result)
recur(node.right, result)
result.append(node.val)
result = []
recur(root, result)
return result
# Example Tree
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
print(postorderTraversal(root))
Output: [4, 5, 2, 6, 7, 3, 1]
This snippet defines a binary tree structure and a recursive function for postorder traversal. The recur() function is an inner function that accesses the result list from its containing scope, appending each node’s value to the result after its children have been visited.
Method 2: Iterative Using Two Stacks
Iterative postorder traversal can be implemented using two stacks, emulating the recursive function call stack. The first stack is used to process nodes in pre-postorder (root->right->left), and the second stack reverses this order to achieve postorder.
Here’s an example:
def postorderTraversalIterative(root):
if root is None:
return []
stack1, stack2 = [root], []
result = []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
while stack2:
result.append(stack2.pop().val)
return result
# Example usage with the same tree structure as above
print(postorderTraversalIterative(root))
Output: [4, 5, 2, 6, 7, 3, 1]
This snippet demonstrates an iterative approach with two stacks, where the first stack is used for processing nodes and the second stack for reversing the order to match postorder traversal. We traverse nodes in a modified pre-order traversal (root, right, left) to stack1 and then transfer to stack2 to reverse the order.
Method 3: Iterative Using One Stack
With a careful design, postorder traversal can be performed iteratively using just one stack. This approach saves space but increases the complexity of the code, as it needs to distinguish between traversing down the tree and processing nodes on the way up.
Here’s an example:
def postorderTraversalSingleStack(root):
if root is None:
return []
stack = []
result = []
current = root
while stack or current:
if current:
stack.append(current)
current = current.left
else:
temp = stack[-1].right
if temp is None:
temp = stack.pop()
result.append(temp.val)
while stack and temp == stack[-1].right:
temp = stack.pop()
result.append(temp.val)
else:
current = temp
return result
# Example usage with the same tree structure as before
print(postorderTraversalSingleStack(root))
Output: [4, 5, 2, 6, 7, 3, 1]
In this code snippet, we maintain a single stack to keep track of the traversal. The current pointer traverses down the left children and adds nodes to the stack. When there’s nowhere left to go, it checks for right children and processes the nodes as it unwinds the stack when coming back up the tree.
Method 4: Morris Traversal (Threaded Binary Trees)
Morris traversal is a complex and advanced technique that uses threaded binary trees to perform traversal without using extra space for a stack or recursion. It modifies the tree by adding temporary links but restores the original tree by the end of the traversal.
Here’s an example:
# Note: Morris Traversal modifies the tree during execution but restores it back to the original state
def postorderTraversalMorris(root):
dummy = TreeNode(0)
dummy.left = root
current = dummy
result = []
while current:
if current.left is None:
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
current = current.left
else:
predecessor.right = None
addPath(result, current.left)
current = current.right
return result
def addPath(result, node):
count = 0
while node:
count += 1
result.append(node.val)
node = node.right
result[-count:] = result[-1:-count-1:-1] # reverse the path
# Example usage with the same tree as before
print(postorderTraversalMorris(root))
Output: [4, 5, 2, 6, 7, 3, 1]
The Morris traversal code snippet ingeniously modifies the tree by threading nonexistent right pointers back to their parent nodes, allowing the algorithm to move back up the tree without a stack. After processing the left subtree, these changes are reverted, and the postorder sequence is obtained by temporarily inverting sections of the tree to allow backward traversal.
Bonus One-Liner Method 5: Using Built-in Functions
Python’s yield from syntax with recursive generators can be employed to create an elegant one-liner for postorder traversal.
Here’s an example:
def postorderTraversalOneliner(root):
return list(postorderGen(root))
def postorderGen(node):
if node:
yield from postorderGen(node.left)
yield from postorderGen(node.right)
yield node.val
# Example usage with the same tree structure
print(postorderTraversalOneliner(root))
Output: [4, 5, 2, 6, 7, 3, 1]
This snippet showcases the beauty of Python’s generator functions and the yield from syntax. With just a few lines of code, postorder traversal is elegantly reduced to its essence, utilizing Python’s built-in capabilities for concise and readable code.
Summary/Discussion
- Method 1: Recursive Traversal. It is the most straightforward and easiest to understand. However, it can lead to stack overflow with exceptionally deep trees.
- Method 2: Iterative Using Two Stacks. This non-recursive method avoids stack overflow and is simple to grasp but uses additional memory for the second stack.
- Method 3: Iterative Using One Stack. More memory-efficient than two-stack solutions, yet it is more complex and harder for some to follow.
- Method 4: Morris Traversal (Threaded Binary Trees). Offers an in-place traversal without additional memory, but it is more complex and risks modifying the tree temporarily, which could be problematic in multi-threaded or real-time systems.
- Bonus One-Liner Method 5: Using Built-in Functions. This method is elegant and efficient if you’re comfortable with generators. It’s not iterative and could still suffer from the maximum recursion depth, similar to the first method.