#145

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Postorder Traversal

Solve Binary Tree Postorder Traversal using state tracking and binary-tree traversal techniques, focusing on Stack, Tree, and DFS.

stack tree depth first search binary tree

Problem Statement

Given the root of a binary tree, perform a postorder traversal and return the list of node values in postorder sequence. Postorder traversal visits the left subtree, then the right subtree, and finally the root node.

For example, consider the tree with root = [1,null,2,3]. The correct postorder traversal is [3,2,1], visiting the leftmost child first, then traversing back to the parent node.

Examples

Example 1

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

Output: [3,2,1]

Example 2

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

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

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Use a Stack for Traversal

In postorder traversal, the last node to be processed is the root. Use a stack to iterate over the tree, ensuring that each node is visited after its children.

Track State for Efficient Traversal

Track the state of each node (whether it's been processed or not) using a stack. Push nodes onto the stack as you traverse down the tree and only pop them when all their children have been visited.

Reverse Postorder with a Stack

Postorder traversal can be simulated by using a stack to first process nodes in reverse (root-right-left), then reversing the result at the end to obtain the correct order.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) as each node is visited once. The space complexity is O(1) when using iterative methods with constant space for the stack, not counting the output list.

What Interviewers Usually Probe

A correct solution requires tracking the traversal state to avoid revisiting nodes.
Look for the candidate’s ability to optimize space usage with stack-based solutions.
Candidates should be able to describe postorder traversal in detail, including why root is visited last.

Common Pitfalls or Variants

Common pitfalls

Failing to properly manage the stack and state tracking may lead to incorrect results.
Misunderstanding the traversal order can result in an incorrect sequence, especially when reversing the stack output.
Forgetting edge cases, like empty trees, where the result should be an empty list.

Follow-up variants

Using a recursive approach instead of a stack-based solution.
Adding constraints to the problem, such as limiting the tree depth or node values.
Modifying the traversal order, such as pre-order or in-order traversal, to test flexibility with different traversal strategies.

FAQ

What is Binary Tree Postorder Traversal?

It is a tree traversal method where the left subtree is visited first, then the right subtree, and finally the root node.

How do I approach Binary Tree Postorder Traversal using a stack?

Use a stack to simulate postorder traversal by visiting nodes in reverse order (root-right-left), then reversing the output to obtain the correct sequence.

What are the time and space complexities for this problem?

The time complexity is O(n), and the space complexity is O(1) when using an iterative stack-based solution.

How does GhostInterview help with this type of problem?

GhostInterview provides step-by-step guidance, helping you implement an efficient solution while avoiding common pitfalls in postorder traversal.

What should I do if I encounter an empty binary tree in this problem?

If the tree is empty, simply return an empty list as there are no nodes to traverse.

terminal

Solution

Solution 1: Recursion

We first recursively traverse the left and right subtrees, then visit the root node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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

Solution 2: Stack Implementation for Postorder Traversal

The order of preorder traversal is: root, left, right. If we change the order of the left and right children, the order becomes: root, right, left. Finally, reversing the result gives us the postorder traversal result.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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

Solution 3: Morris Implementation for Postorder Traversal

Morris traversal does not require a stack, and its space complexity is $O(1)$. The core idea is:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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

Continue Practicing

#144 binary tree preorder traversal #114 flatten binary tree to linked list #94 binary tree inorder traversal