Binary Tree Postorder Traversal

Problem Summary

• Given a root of the tree, return a post-order traversal result of its values

Why This Works

• For the iterative solution, we are basically doing a Pre-order Traversal with a slight hack of adding left node first instead of the usual right node. Then at the end reversing the output to convert pre-order to a post-order.

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Trees
• Tree Traversal
• Post-order Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Processing each node
• Space: $O(n)$ → Reason: Could have all nodes in the stack

Recursive Code

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
	    result = []
        def dfs(root):
	        if not root:
		        return
		    dfs(root.left)
		    dfs(root.right)
		    result.append(root.val)
		dfs(root)
		return result

Iterative Code

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            if node:
                result.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        result.reverse()
        return result