Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0145 - Binary Tree Postorder Traversal
    0145 - Binary Tree Postorder Traversal
    0145 - Binary Tree Postorder Traversal
    0145 - Binary Tree Postorder Traversal

    0145 - Binary Tree Postorder Traversal

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/binary-tree-postorder-traversal/

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)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()

    """ 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()