Post-order Traversal

Post-order traversal follows the "left, right, root" order. For each node, the algorithm recursively traverses the left subtree, then recursively traverses the right subtree, and finally processes the node itself. This traversal method is commonly used to delete a tree, as it ensures that a node's children are deleted before the node itself.

Post-Order Traversal (Tree)

Step 1 of 0

Action

Ready to start

Current Node

None

Call Stack

[]

Traversal Order

[]

Current Node

Visited

In Call Stack

Unvisited

Post-order Traversal Algorithm

Post-order traversal follows the "left, right, root" order. This means for each node, the algorithm recursively traverses the left subtree, then the right subtree, and finally processes the node itself. It's commonly used to delete a tree, as a node can be deleted after its children are deleted.

Algorithm Steps (Recursive)

Recursively call post-order traversal on the left child, if it exists.
Recursively call post-order traversal on the right child, if it exists.
Visit the current node (e.g., add its value to a list).
The base case for the recursion is when a node is null.

Recursive Post-order Traversal


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)
            
        dfs(root)
        return res

Iterative Post-order Traversal

The iterative approach for post-order traversal is a bit more complex than pre-order and in-order. A common method uses two stacks.

Algorithm Steps (Two Stacks)

Initialization: Create two stacks, `s1` and `s2`. Push the root node to `s1`.
Loop: While `s1` is not empty, do the following:
Pop a node from `s1` and push it to `s2`.
Push the left child of the popped node to `s1`.
Push the right child of the popped node to `s1`.
Result: After the loop, pop all elements from `s2` and add them to the result list. The result will be in post-order.

Iterative Post-order Traversal


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
            
        s1, s2 = [root], []
        res = []
        
        while s1:
            node = s1.pop()
            s2.append(node)
            if node.left:
                s1.append(node.left)
            if node.right:
                s1.append(node.right)
                
        while s2:
            res.append(s2.pop().val)
            
        return res