Difficulty: Easy | Acceptance: 78.10% | Paid: No Topics: Stack, Tree, Depth-First Search, Binary Tree
Given the root of a binary tree, return the postorder traversal of its nodes’ values.
Table of Contents
- Examples
- Constraints
- Recursive Depth-First Search
- Iterative Depth-First Search
- Morris Traversal
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 4
Input:
root = [1]
Output:
[1]
Constraints
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Recursive Depth-First Search
Intuition Postorder traversal follows the Left-Right-Root sequence. We can naturally implement this using recursion by traversing the left subtree, then the right subtree, and finally processing the current node.
Steps
- Check if the root is null. If so, return an empty list.
- Recursively call the function for the left subtree.
- Recursively call the function for the right subtree.
- Append the current node’s value to the result list.
- Return the result list.
python
from typing import List, Optional
# 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]:
result = []
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
result.append(node.val)
dfs(root)
return result
Complexity
- Time: O(n) where n is the number of nodes.
- Space: O(h) where h is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this is O(n).
- Notes: Simple and readable, but may cause a stack overflow for very deep trees.
Iterative Depth-First Search
Intuition We can simulate the recursion using an explicit stack. A common trick for iterative postorder traversal is to perform a modified preorder traversal (Root-Right-Left) and then reverse the result. This yields Left-Right-Root.
Steps
- Initialize a stack with the root node and an empty result list.
- While the stack is not empty:
- Pop the top node from the stack.
- Add the node’s value to the result list.
- Push the left child onto the stack (if it exists).
- Push the right child onto the stack (if it exists).
- Since we processed Root-Right-Left, reverse the result list to get Left-Right-Root.
- Return the result.
python
from typing import List, Optional
# 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]:
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
Complexity
- Time: O(n) where n is the number of nodes.
- Space: O(n) for the stack storage.
- Notes: Avoids recursion depth limits but uses extra space proportional to the number of nodes.
Morris Traversal
Intuition Morris Traversal allows us to traverse the tree with O(1) extra space (excluding the output list) by temporarily modifying the tree structure (threaded binary tree). For postorder, we use a dummy node and reverse the path between the current node and its predecessor when we find a loop.
Steps
- Create a dummy node that points to the root. Set current to this dummy node.
- While current is not null:
- If current has no left child, move current to current.right.
- Else, find the predecessor of current (the rightmost node in the left subtree).
- If predecessor.right is null, link it to current and move current to current.left.
- If predecessor.right is current, we have visited the left subtree. Break the link, reverse the path from current.left to predecessor, add values to result, and move current to current.right.
- Return the result.
python
from typing import List, Optional
# 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]:
result = []
def reverse_path(start, end):
# Reverse the linked list nodes from start to end
prev = None
curr = start
while curr != end:
next_temp = curr.right
curr.right = prev
prev = curr
curr = next_temp
# curr is end, prev is the new head of reversed segment
return prev
def visit_reverse(start, end):
# Visit nodes from start to end (which are currently reversed)
# Then reverse them back to original state
first = start
curr = start
while True:
result.append(curr.val)
if curr == end:
break
curr = curr.right
# Restore the tree structure
reverse_path(start, end)
start.right = end
dummy = TreeNode(0)
dummy.left = root
curr = dummy
while curr:
if curr.left is None:
curr = curr.right
else:
pre = curr.left
while pre.right and pre.right != curr:
pre = pre.right
if pre.right is None:
pre.right = curr
curr = curr.left
else:
visit_reverse(curr.left, pre)
pre.right = None
curr = curr.right
return result
Complexity
- Time: O(n) where n is the number of nodes. Each node is visited a constant number of times.
- Space: O(1) auxiliary space (excluding the output list).
- Notes: Modifies the tree structure temporarily but restores it. Most space-efficient but complex to implement.