Algocademy Logo

Post Order Tree Traversal in Python (Time Complexity: O(n))


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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

Understanding the Problem

The core challenge of this problem is to traverse a binary tree in postorder, which means visiting the left subtree, then the right subtree, and finally the root node. This traversal is significant in various applications such as expression tree evaluations and syntax tree traversals in compilers.

Potential pitfalls include misunderstanding the traversal order and handling null nodes incorrectly.

Approach

To solve this problem, we can consider both recursive and iterative approaches:

Recursive Approach

The recursive approach is straightforward. We define a function that recursively visits the left subtree, then the right subtree, and finally appends the root node's value to the result list.

Iterative Approach

The iterative approach is more complex but can be achieved using a stack. We use two stacks to simulate the postorder traversal. The first stack is used to traverse the tree, and the second stack is used to store the nodes in postorder.

Algorithm

Recursive Approach

  1. Define a helper function that takes a node and a result list as arguments.
  2. If the node is not null, recursively call the helper function on the left child.
  3. Recursively call the helper function on the right child.
  4. Append the node's value to the result list.

Iterative Approach

  1. Initialize two stacks: one for traversal and one for storing the postorder result.
  2. Push the root node onto the first stack.
  3. While the first stack is not empty:
    1. Pop a node from the first stack and push it onto the second stack.
    2. Push the left and right children of the popped node onto the first stack.
  4. Pop all nodes from the second stack and append their values to the result list.

Code Implementation

Recursive Solution

def postorder_traversal_recursive(root):
    def helper(node, result):
        if node:
            helper(node.left, result)  # Traverse left subtree
            helper(node.right, result)  # Traverse right subtree
            result.append(node.val)  # Visit root node

    result = []
    helper(root, result)
    return result

Iterative Solution

def postorder_traversal_iterative(root):
    if not root:
        return []

    stack1, stack2 = [root], []
    result = []

    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)  # Push left child to stack1
        if node.right:
            stack1.append(node.right)  # Push right child to stack1

    while stack2:
        node = stack2.pop()
        result.append(node.val)  # Collect nodes in postorder

    return result

Complexity Analysis

Both the recursive and iterative solutions have a time complexity of O(n), where n is the number of nodes in the tree. This is because each node is visited exactly once.

The space complexity for the recursive solution is O(h), where h is the height of the tree, due to the call stack. For the iterative solution, the space complexity is O(n) due to the use of two stacks.

Edge Cases

Potential edge cases include:

Testing

To test the solution comprehensively, consider the following test cases:

Thinking and Problem-Solving Tips

When approaching tree traversal problems, it is helpful to:

Conclusion

Postorder tree traversal is a fundamental problem in computer science with various applications. Understanding both recursive and iterative approaches is crucial for solving more complex tree-related problems. Practice and familiarity with different traversal techniques will improve your problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: