Solution 1 - Recursive DFS

Given the root of a binary tree, return the postorder traversal of its nodes' values. Postorder traversal visits nodes in the order: left subtree, right subtree, then the root node. The recursive approach naturally mirrors this definition — recursively traverse left, then right, then append the current node's value.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0145.1 - Binary Tree Postorder Traversal - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """Postorder Traversal Function"""
        result = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)

        dfs(root)
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1, null, 2, 3] -> [3, 2, 1]
    root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(Solution().postorderTraversal(root1))

    # [] -> []
    print(Solution().postorderTraversal(None))

    # [1] -> [1]
    root3 = TreeNode(1)
    print(Solution().postorderTraversal(root3))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Iterative using Stack

Instead of recursion, use an explicit stack. The trick is to traverse in a modified preorder (root → right → left) and then reverse the result to get postorder (left → right → root). We push left first, then right onto the stack, so right is processed first. Appending to the front of the result list (or reversing at the end) gives us the correct postorder.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0145.2 - Binary Tree Postorder Traversal - Solution 2 - Iterative using Stack """

#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """Postorder Traversal Function"""
        if not root:
            return []

        stack = [root]
        result = []

        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        return result[::-1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1, null, 2, 3] -> [3, 2, 1]
    root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(Solution().postorderTraversal(root1))

    # [] -> []
    print(Solution().postorderTraversal(None))

    # [1] -> [1]
    root3 = TreeNode(1)
    print(Solution().postorderTraversal(root3))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0145 - Binary Tree Postorder Traversal

Solution 1 - Recursive DFS

Solution 2 - Iterative using Stack