Postorder Traversal of Binary Tree without Recursion and without Stack

Table of Content#

Understanding Binary Tree Postorder Traversal
Traditional Approaches (Recursion and Stack)
- Recursive Postorder Traversal
- Iterative Postorder Traversal with Stack
The Alternative Approach (Without Recursion and Stack)
- Using Morris Postorder Traversal
Example Usage
Best Practices and Considerations
References

Understanding Binary Tree Postorder Traversal#

In a binary tree, each node can have at most two children (left and right). Postorder traversal follows the order: left child → right child → root. For example, in the simple binary tree:

     1
   /   \
  2     3

The postorder traversal would be 2, 3, 1.

Traditional Approaches (Recursion and Stack)#

Recursive Postorder Traversal#

The recursive approach is straightforward. The base case is when the current node is null. Otherwise, we recursively traverse the left subtree, then the right subtree, and finally visit the root node.

Here's the Python code for recursive postorder traversal:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def postorderTraversalRecursive(root):
    result = []
    def helper(node):
        if node:
            helper(node.left)
            helper(node.right)
            result.append(node.val)
    helper(root)
    return result

Iterative Postorder Traversal with Stack#

In the iterative approach with a stack, we use two stacks. One stack is used to push the nodes in a way that allows us to reverse the order later. We first push the root node onto the first stack. Then, while the first stack is not empty, we pop a node, push it onto the second stack, and then push its left and right children (if they exist) onto the first stack. Finally, we pop elements from the second stack to get the postorder traversal.

Here's the Python code:

def postorderTraversalIterativeWithStack(root):
    if not root:
        return []
    stack1 = [root]
    stack2 = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    result = []
    while stack2:
        result.append(stack2.pop().val)
    return result

The Alternative Approach (Without Recursion and Stack)#

Using Morris Postorder Traversal#

Morris postorder traversal is a space-efficient technique that uses the existing null right pointers in the tree to create temporary threads back to ancestor nodes. This allows us to traverse the tree without a stack or recursion. The key insight is that by reversing the path from the left subtree back to the predecessor during backtracking, we can collect nodes in the correct postorder sequence.

Algorithm Steps#

Initialize current to root, and create a dummy node pointing to root.
While current is not null:
- If current has no left child:
  - Move current to its right child.
- Else:
  - Find the in-order predecessor of current (the rightmost node in current's left subtree).
  - If the predecessor's right child is null:
    - Set the predecessor's right child to current (creating a thread).
    - Move current to its left child.
  - Else (the predecessor's right child points to current, meaning we've returned from the left subtree):
    - Reverse the path from current.left to predecessor.
    - Collect node values from predecessor back to current.left (in postorder of left subtree).
    - Restore the path by reversing again.
    - Set predecessor's right child back to null.
    - Move current to its right child.
After the main loop, collect the remaining right spine of the tree.
Reverse the final result to obtain correct postorder.

Here's the Python code implementation:

def postorderTraversalMorris(root):
    result = []
    dummy = TreeNode(0)
    dummy.left = root
    current = dummy
    
    while current:
        if not current.left:
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                temp = current.left
                path_rev = []
                while temp != predecessor:
                    path_rev.append(temp.val)
                    temp = temp.right
                path_rev.append(predecessor.val)
                for i in range(len(path_rev) - 1, -1, -1):
                    result.append(path_rev[i])
                current = current.right
    
    temp = root
    right_spine = []
    while temp:
        right_spine.append(temp.val)
        temp = temp.right
    result.extend(right_spine)
    
    i, j = 0, len(result) - 1
    while i < j:
        result[i], result[j] = result[j], result[i]
        i += 1
        j -= 1
    
    return result

The Morris postorder algorithm works by threading the tree and processing the left subtree in reverse order when we backtrack, then reversing the entire collected sequence to get the correct postorder output.

Example Usage#

Let's create a sample binary tree and test our functions:

# Create a sample binary tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
 
# Test recursive function
print("Recursive Postorder Traversal:", postorderTraversalRecursive(root))
 
# Test iterative with stack function
print("Iterative with Stack Postorder Traversal:", postorderTraversalIterativeWithStack(root))
 
# Test the without stack/recursion function
print("Postorder Traversal without Stack/Recursion:", postorderTraversalMorris(root))

Best Practices and Considerations#

Code Readability: The code for the without stack/recursion approach can be a bit complex. It's a good practice to add detailed comments to make it understandable.
Error Handling: Make sure to handle cases where the input tree is null gracefully in all functions.
Performance: While the without stack/recursion approach avoids the stack memory overhead, it has a more complex logic. In practice, for most applications, the recursive or stack-based iterative approaches are more straightforward and may have comparable performance unless dealing with extremely large trees where stack overflow is a real concern.

References#

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.