Leetcode – Binary Tree Postorder Traversal Solution in Python

Spread the love

Binary trees are a fundamental data structure in computer science. Traversing a binary tree is one of the primary operations that provide a foundation for more complex algorithms. In this comprehensive article, we will tackle the Binary Tree Postorder Traversal problem listed on LeetCode, explore different strategies for solving it, and implement these solutions in Python.

Problem Statement

The Binary Tree Postorder Traversal problem is listed as problem number 145 on LeetCode. Here’s the problem statement:

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]

Understanding the Problem

In this problem, we are given the root of a binary tree, and our task is to return a list containing the values of the nodes in their postorder traversal order. In postorder traversal, each node is visited in the following order: Left -> Right -> Node. This means that we first recursively visit the left subtree, then the right subtree, and finally the current node.

Approach 1: Recursive Solution

One of the most straightforward solutions to this problem is to use recursion. We create a helper function that takes a node and a list. If the node is not null, we recursively call the function for the left child, then for the right child, and finally, add the node’s value to the list.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root):
    def helper(node, result):
        if node:
            helper(node.left, result)
            helper(node.right, result)
            result.append(node.val)
    
    result = []
    helper(root, result)
    return result

This approach has a time complexity of O(n), where n is the number of nodes in the tree, as each node is visited once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.

Approach 2: Iterative Solution using Two Stacks

We can also perform postorder traversal iteratively by using two stacks. This method is a little trickier than the recursive approach but is valuable in situations where recursion is not ideal.

Here’s how the iterative solution using two stacks works:

  1. Push the root to the first stack.
  2. Pop a node from the first stack, and push it to the second stack.
  3. Push the left and right children of the popped node to the first stack.
  4. Repeat steps 2 and 3 until the first stack is empty.
  5. Pop nodes from the second stack and add them to the result list.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root):
    if not root:
        return []
    
    stack1, stack2, result = [root], [], []
    
    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.val)
    
    return result

This iterative approach also has a time complexity of O(n), and a space complexity of O(h). However, it uses two stacks, so it consumes more space than the recursive approach.

Understanding the Choices

While both recursive and iterative approaches achieve the same result, they differ in their implementation. The recursive approach is more concise but might not be feasible for very deep trees due to stack overflow. The iterative approach using two stacks is more explicit in its handling of the node ordering and doesn’t have the same restrictions regarding the depth of the tree.

Conclusion

Postorder traversal is one of the fundamental operations that one can perform on a binary tree. Understanding both recursive and iterative methods for postorder traversal is essential as these concepts are not only applicable to binary trees but form the foundation for traversal on other tree-like structures.

In coding interviews, explaining both recursive and iterative solutions and the trade-offs between them can demonstrate a strong understanding of data structures and algorithms. In production code, the choice between the two methods might be influenced by factors such as the expected depth of the trees being handled.

Leave a Reply