# 0145. Postorder Traversal

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0145-binary-tree-postorder-traversal)

Given the `root` of a binary tree, return *the **postorder traversal** of its nodes' values*.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of the nodes in the tree is in the range `[0, 100]`.
* `-100 <= Node.val <= 100`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Postorder traversal **stops iterating when there is no left-child node**.

In other words, we need to **keep non-visited nodes along the path**.
{% endhint %}

**Pop the stack** to retrieve the tuple/pair with the current node and ***visited status***.

* If already being visited, we could append the node's value to the answer.
* If not:
  * First, push the **current node but with visited status**
  * Second, push the **right-child node with non-visited status** (if the node exists)
  * Last, push the **left-child node** with non-visited status (if the node exists)
    {% endtab %}
    {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [root.val]
        
        # ==================================================
        #  Binary Tree + Post-order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [(root, False)]
        
        while stack:
            node, visited = stack.pop()
            
            if node:
                if visited:
                    ans.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
                    
        return ans
    
        '''
        # ==================================================
        #  Binary Tree + Post-order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
        '''
```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public List<Integer> postorderTraversal(TreeNode root) {
        /* base case */
        if(root == null) return new ArrayList<>();
        
        List<Integer> result = new ArrayList<>();
        Stack<Pair<TreeNode, Boolean>> stack = new Stack<Pair<TreeNode, Boolean>>();
        stack.push(new Pair<TreeNode, Boolean>(root, false));
        
        while(!stack.isEmpty()) {
            Pair<TreeNode, Boolean> object = stack.pop();
            TreeNode node = object.getKey();
            Boolean visited = object.getValue();
            
            if(visited == true) result.add(node.val);
            else {
                stack.push(new Pair<TreeNode, Boolean>(node, true));
                if(node.right != null) stack.push(new Pair<TreeNode, Boolean>(node.right, false));
                if(node.left != null) stack.push(new Pair<TreeNode, Boolean>(node.left, false));
            }
        }
        
        return result;
    }
}
```

{% endtab %}
{% endtabs %}