DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Binary Tree Postorder Traversal - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

# 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]:
        result = []

        def postorder(node):
            if not node:
                return None

            postorder(node.left)
            postorder(node.right)
            result.append(node.val)
        
        postorder(root)
        return result

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space: O(n) — to store the final postorder traversal result (list of node values)
    • Stack space: O(h) — for the recursion stack.
      • In the best case (a balanced tree), h = log n.
      • In the worst case (a skewed tree), h = n, so the recursion stack uses O(n) space.

# 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]:
        result = []
        stack = [root]

        while stack:
           cur = stack.pop()
           if cur:
               result.append(cur.val)
               stack.append(cur.left)
               stack.append(cur.right)
        return result[::-1]          # Reverse to get postorder

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)
    • Each node is visited during traversal.
  • Space Complexity: O(n)
    • Output space: O(n) — to store the final postorder traversal result (list of node values)
    • Stack space: O(h) — for the explicit stack used in traversal. In the worst case, h can be up to n.