How hard is LeetCode 145. Binary Tree Postorder Traversal?

LeetCode 145. Binary Tree Postorder Traversal is rated Easy on LeetCode.

What is the time complexity of LeetCode 145. Binary Tree Postorder Traversal?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 145. Binary Tree Postorder Traversal?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 145. Binary Tree Postorder Traversal cover?

LeetCode 145. Binary Tree Postorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.

Binary Tree Postorder Traversal — LeetCode 145 Python Solution

EasyStackTreeDepth-First SearchBinary Tree

Problem: #145
Pattern: Stack
Reading time: 3 min
Source: leetcode.com

The problem

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

Python solution

Python

# 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]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            dfs(root.right)
            ans.append(root.val)

        ans = []
        dfs(root)
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 145. Binary Tree Postorder Traversal is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 145. Binary Tree Postorder Traversal?: LeetCode 145. Binary Tree Postorder Traversal is rated Easy on LeetCode.
What is the time complexity of LeetCode 145. Binary Tree Postorder Traversal?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 145. Binary Tree Postorder Traversal?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 145. Binary Tree Postorder Traversal cover?: LeetCode 145. Binary Tree Postorder Traversal is tagged Stack, Tree, Depth-First Search and Binary Tree on LeetCode.