---
tags: data_structure_python
---

# Binary Tree Postorder Traversal <img src="https://img.shields.io/badge/-easy-brightgreen">

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

**Example:**

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

**Follow up:** Recursive solution is trivial, could you do it iteratively?

# Solution

### Solution 1: Recursive

# 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: TreeNode) -> List[int]:
        def dfs(root, res):
            if root != None:
                dfs(root.left, res)
                dfs(root.right, res)
                res.append(root.val)
        res = []
        dfs(root, res)
        return res

### Solution 2: Iterative

# 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: TreeNode) -> List[int]:
        res, stack = [], [(root, False)]
        while len(stack) > 0:
            node, visited = stack.pop()  
            if node != None:
                if visited:
                    res.append(node.val)
                else: 
                    stack.append((node, True)) # Postorder.
                    stack.append((node.right, False))
                    # stack.append((node, True)) # Inorder.
                    stack.append((node.left, False))
                    # stack.append((node, True)) # Preorder.
        return res