145. Binary Tree Postorder Traversal - Explanation

Description

You are given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [4,5,2,6,7,3,1]

Example 2:

Input: root = [1,2,3,null,4,5,null]

Output: [4,2,5,3,1]

Example 3:

Input: root = []

Output: []

Constraints:

0 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

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

        def postorder(node):
            if not node:
                return

            postorder(node.left)
            postorder(node.right)
            res.append(node.val)

        postorder(root)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(n)$ space for the recursion stack.
- $O(n)$ space for the output array.

2. Iterative Depth First Search - I

# 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]:
        stack = [root]
        visit = [False]
        res = []

        while stack:
            cur, v = stack.pop(), visit.pop()
            if cur:
                if v:
                    res.append(cur.val)
                else:
                    stack.append(cur)
                    visit.append(True)
                    stack.append(cur.right)
                    visit.append(False)
                    stack.append(cur.left)
                    visit.append(False)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(n)$ space for the stacks.
- $O(n)$ space for the output array.

3. Iterative Depth First Search - II

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

        while cur or stack:
            if cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right
            else:
                cur = stack.pop()
                cur = cur.left

        res.reverse()
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(n)$ space for the stack.
- $O(n)$ space for the output array.

4. Morris Traversal

# 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]:
        res = []
        cur = root

        while cur:
            if not cur.right:
                res.append(cur.val)
                cur = cur.left
            else:
                prev = cur.right
                while prev.left and prev.left != cur:
                    prev = prev.left

                if not prev.left:
                    res.append(cur.val)
                    prev.left = cur
                    cur = cur.right
                else:
                    prev.left = None
                    cur = cur.left

        res.reverse()
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.