069.md

145. Binary Tree Postorder Traversal

Difficulty: 🟢 Easy

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Examples:

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solutions

O(n) solution

Python 3

# 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 []

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

The given solution provides an iterative approach to perform a postorder traversal of a binary tree.

Here is a step-by-step overview of the solution:

1. Check if the root is None. If it is, return an empty list as there are no nodes to traverse.
2. Initialize an empty list result to store the postorder traversal and a stack with the root node.
3. Enter a loop that continues until the stack is not empty:
   • Pop a node from the stack.
   • Append the value of the node to the result.
   • If the node has a left child, push the left child to the stack.
   • If the node has a right child, push the right child to the stack.
4. Reverse the result list.
5. Return the result, which contains the postorder traversal of the binary tree.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the stack can contain all nodes along the path from the root to the leftmost leaf.

Summary

The given solution provides an iterative approach to perform a postorder traversal of a binary tree. It uses a stack to keep track of the nodes to visit and appends the node values to the result list in postorder. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the binary tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.