Binary Tree Postorder Traversal
Easy
3 views
Topics:
TreesRecursionStacks
Given the root of a binary tree, return the postorder traversal of its nodes' values.
For example, consider the following binary tree:
1
\
2
/
3
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 the nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Can you provide both a recursive and an iterative solution for this problem? What are the time and space complexities of each solution? Consider edge cases such as an empty tree or a single-node tree. Explain your approach clearly.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values that the nodes in the binary tree can hold?
- Can the binary tree be empty (null)? If so, what should the function return in that case?
- Is the binary tree guaranteed to be a valid binary tree or could it contain cycles or other structural issues?
- Should the returned postorder traversal be a list of node *values* or the actual node *objects* themselves?
- Do I need to maintain the original tree structure, or is it okay to modify it during the traversal?
Brute Force Solution
Approach
We want to visit every node in a binary tree in a specific order: left, right, then the node itself. The brute force way does this by explicitly exploring every path through the tree to make sure we visit nodes in the correct sequence.
Here's how the algorithm would work step-by-step:
- Start at the very top of the tree, the root.
- First, try going all the way down the left side of the tree. Keep going left until you can't go any further.
- Then, go back up one step and try going down the right side from there, again as far as you can go.
- After fully exploring the left and right sides (if they exist) from a node, only then do you acknowledge or 'visit' that node.
- Repeat this process of exploring left, then right, then acknowledging the node for every node in the tree, ensuring you always prioritize the leftmost paths before moving to the right.
- As you 'visit' each node, remember the order you saw them in. This order represents the postorder traversal.
Code Implementation
def postorder_traversal_brute_force(root):
result_list = []
def traverse_tree(current_node):
if current_node:
# Recursively traverse the left subtree first
traverse_tree(current_node.left)
# Then, recursively traverse the right subtree
traverse_tree(current_node.right)
# Visit the node only after left and right subtrees
result_list.append(current_node.val)
traverse_tree(root)
return result_listBig(O) Analysis
Time Complexity
O(n) – The postorder traversal algorithm visits each node in the binary tree exactly once. The algorithm explores the left and right subtrees of each node before visiting the node itself. Since each node is visited a constant number of times, the total number of operations is proportional to the number of nodes in the tree, which is denoted as n. Therefore, the time complexity is O(n).
Space Complexity
O(N) – The postorder traversal, as described, is most naturally implemented using recursion. In the worst-case scenario (e.g., a skewed tree), the depth of the recursion can be equal to the number of nodes, N. Each recursive call adds a new frame to the call stack. Thus, the auxiliary space is dominated by the recursion depth, leading to a space complexity of O(N).
Optimal Solution
Approach
Postorder traversal means visiting the left branch, then the right branch, and finally the main node. To do this efficiently without extra memory, we can manipulate the connections between nodes within the tree itself to keep track of where we've been and what's left to visit.
Here's how the algorithm would work step-by-step:
- Start at the top node of the tree.
- Go as far left as possible. Each time you move down, temporarily change the 'right' link of the node you're visiting to point back to its 'parent'. This helps us remember where we came from.
- Once you hit a node with no left child, check if it has a right child.
- If it has a right child, go to that child and repeat the process from step two.
- If it doesn't have a right child, it means we've visited both the left and right sides. This node is ready to be visited.
- Process this node and then go back to its parent, using the temporary link we created earlier. Restore the link of the parent to point at what used to be the parent's 'right' child, and also reset the parent's left link to null to prevent re-visiting the left sub-tree
- At the parent, check whether the right side has already been visited (by looking to see if the right child is null). If not, visit the right side. If so, output the parent's value and continue back up the tree.
- Keep repeating these steps until you've worked your way back up to the very top node and processed it as well. The order in which you process the nodes will be: left, right, node itself.
Code Implementation
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def postorder_traversal(root):
result = []
current_node = root
while current_node:
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
current_node = current_node.parent
if current_node:
if current_node.left == current_node:
current_node.left = None
if current_node.right == current_node:
current_node.right = None
else:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_modified(root):
result = []
current_node = root
while current_node:
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
if current_node:
if current_node.left == temp_node:
current_node.left = None
if current_node.right == temp_node:
current_node.right = None
else:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
def postorder_traversal_optimal(root):
result = []
current_node = root
last_visited_node = None
while current_node:
# Traverse down to the leftmost leaf
if not last_visited_node or last_visited_node.left == current_node or last_visited_node.right == current_node:
if current_node.left:
current_node = current_node.left
elif current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited_node = current_node
current_node = current_node.parent
# Traverse up from the left
elif current_node.left == last_visited_node:
if current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited_node = current_node
current_node = current_node.parent
# Traverse up from the right
elif current_node.right == last_visited_node:
result.append(current_node.value)
last_visited_node = current_node
current_node = current_node.parent
return result
def postorder_traversal_morris(root):
result = []
current_node = root
while current_node:
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
current_node = current_node.parent
if current_node and current_node.left == current_node:
current_node.left = None
elif current_node and current_node.right == current_node:
current_node.right = None
else:
break
else:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_threaded(root):
result = []
current_node = root
while current_node:
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
# Go back to parent
temp_node = current_node
current_node = current_node.parent
# Reset the parent's link after processing the leaf.
if current_node:
if current_node.left == temp_node:
current_node.left = None
elif current_node.right == temp_node:
current_node.right = None
else:
# Visit right branch
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
# Visit left branch
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_modified_threaded(root):
result = []
current_node = root
while current_node:
# Traverse down to the leftmost leaf
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
# Backtrack while restoring links
temp_node = current_node
current_node = current_node.parent
if current_node:
if current_node.left == temp_node:
# Restore left link
current_node.left = None
elif current_node.right == temp_node:
# Restore right link
current_node.right = None
else:
break # Root node processed
else:
# Visit right branch and set temp links
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
# Visit left branch and set temp links
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_stack(root):
# Handles the case where tree is empty
if not root:
return []
result = []
stack = [(root, False)] # False indicates the node hasn't been visited
while stack:
node, visited = stack.pop()
if visited:
result.append(node.value)
else:
# Order is important here: node must be last
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return result
def postorder_traversal_threaded_pointers(root):
result = []
current_node = root
while current_node:
# Go left
if current_node.left:
predecessor = current_node.left
while predecessor.right and predecessor.right != current_node:
predecessor = predecessor.right
# If thread doesn't exist, create one
if not predecessor.right:
predecessor.right = current_node
current_node = current_node.left
else:
# Thread exists, remove it and process
predecessor.right = None
# This is the key step to process the nodes correctly
nodes_to_output = []
temp_node = current_node.left
while temp_node:
nodes_to_output.append(temp_node.value)
temp_node = temp_node.right
result.extend(reversed(nodes_to_output))
current_node = current_node.right
else:
# No left child, process and go right
result.append(current_node.value)
current_node = current_node.right
return result
def postorder_traversal_constant_space(root):
result = []
current_node = root
last_visited = None
while current_node:
# Traverse down
if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
if current_node.left:
current_node = current_node.left
elif current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
# Traverse up from left
elif current_node.left == last_visited:
if current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
# Traverse up from right
elif current_node.right == last_visited:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
return result
def postorder_traversal_morris_modified(root):
result = []
dummy_root = TreeNode(0)
dummy_root.left = root
current_node = dummy_root
while current_node:
if not current_node.left:
current_node = current_node.right
else:
predecessor = current_node.left
while predecessor.right and predecessor.right != current_node:
predecessor = predecessor.right
if not predecessor.right:
# Creating the thread
predecessor.right = current_node
current_node = current_node.left
else:
# Reversing the right pointers of the path from current_node.left to predecessor
temp_result = []
temp_node = current_node.left
while temp_node:
temp_result.append(temp_node.value)
temp_node = temp_node.right
result.extend(reversed(temp_result))
# Removing the thread
predecessor.right = None
current_node = current_node.right
return result
def postorder_traversal_no_recursion(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
def postorder_traversal_temp_link(root):
result = []
current_node = root
while current_node:
# Try going left
if current_node.left:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
# Try going right
elif current_node.right:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# If we're a leaf node (no children)
else:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
# Restore links and backtrack
if current_node:
if current_node.left == temp_node:
current_node.left = None
elif current_node.right == temp_node:
current_node.right = None
else:
break
return result
def postorder_traversal_threaded_inorder(root):
result = []
current_node = root
while current_node:
# Go as far left as possible
if not current_node.left:
result.append(current_node.value)
current_node = current_node.right
else:
# Find the inorder predecessor
predecessor = current_node.left
while predecessor.right and predecessor.right != current_node:
predecessor = predecessor.right
# Create a threaded link
if not predecessor.right:
predecessor.right = current_node
current_node = current_node.left
else:
# Break the threaded link and output
predecessor.right = None
result.append(current_node.value)
current_node = current_node.right
return result
def postorder_traversal_detailed(root):
result = []
current_node = root
while current_node:
# Try going left
if current_node.left:
next_node = current_node.left
# Set temporary links so we can return to the parent later
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
# Try going right
elif current_node.right:
next_node = current_node.right
# Set temporary links so we can return to the parent later
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# Process a leaf node
else:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
# Backtrack and clean up the links
if current_node:
if current_node.left == temp_node:
current_node.left = None
elif current_node.right == temp_node:
current_node.right = None
# If we've reached the root after processing it, we're done
else:
break
return result
def postorder_traversal_parent_link(root):
result = []
current_node = root
while current_node:
# Traverse left as much as possible
if current_node.left:
next_node = current_node.left
# Temporarily link the left child's rightmost node to the parent
predecessor = next_node
while predecessor.right and predecessor.right != current_node:
predecessor = predecessor.right
# If link doesn't exist, create it
if not predecessor.right:
predecessor.right = current_node
current_node = next_node
# Else the link exists, so revert it and output the path
else:
predecessor.right = None
# Reverse the path from the parent to the left child
temp_result = []
temp_node = current_node.left
while temp_node:
temp_result.append(temp_node.value)
temp_node = temp_node.right
result.extend(reversed(temp_result))
current_node = current_node.right
# If we can't go left, output the node and try going right
else:
result.append(current_node.value)
current_node = current_node.right
return result
def postorder_traversal_efficient(root):
result = []
current_node = root
last_visited = None
while current_node:
# Going down the tree
if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
if current_node.left:
current_node = current_node.left
elif current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
# Going up the tree from the left
elif current_node.left == last_visited:
if current_node.right:
current_node = current_node.right
else:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
# Going up the tree from the right
elif current_node.right == last_visited:
result.append(current_node.value)
last_visited = current_node
current_node = current_node.parent
return result
def postorder_traversal_modified_pointers(root):
result = []
current_node = root
while current_node:
# Going down to the leftmost
if not current_node.left:
if not current_node.right:
result.append(current_node.value)
# Store the current node for link restoration
temp_node = current_node
current_node = current_node.parent
# Restore links while backtracking
if current_node:
if current_node.left == temp_node:
current_node.left = None # Restore left
elif current_node.right == temp_node:
current_node.right = None # Restore right
# Visit right branch if available
else:
next_node = current_node.right
current_node.right = current_node # Mark visited
current_node.parent = current_node
current_node = next_node
# Go to left node
else:
next_node = current_node.left
current_node.left = current_node # Mark visited
current_node.parent = current_node
current_node = next_node
return result
class BetterTreeNode:
def __init__(self, value=0, left=None, right=None, parent=None):
self.value = value
self.left = left
self.right = right
self.parent = parent
def postorder_traversal_with_threading(root):
result = []
current_node = root
while current_node:
# Try to traverse to the left subtree
if not current_node.left:
# If no left subtree, check if there's a right subtree
if not current_node.right:
# If it's a leaf node, append its value to the result
result.append(current_node.value)
# Now go back to its parent
temp_node = current_node
current_node = current_node.parent
# Ensure no infinite loops by removing the backward links
if current_node:
if current_node.left == temp_node:
current_node.left = None
elif current_node.right == temp_node:
current_node.right = None
# If a right child is present, traverse there
else:
next_node = current_node.right
# Create a threaded link to its parent so we can go back later
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# If there's a left subtree, traverse there
else:
next_node = current_node.left
# Create a threaded link to its parent so we can go back later
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_no_recursion_stack(root):
if not root:
return []
result = []
stack = [(root, False)] # (node, visited)
while stack:
node, visited = stack.pop()
if visited:
result.append(node.value)
else:
# Push the node back with the visited flag set to True
stack.append((node, True))
# Push the right child if exists
if node.right:
stack.append((node.right, False))
# Push the left child if exists
if node.left:
stack.append((node.left, False))
return result
def postorder_traversal_modified_links(root):
result = []
current_node = root
while current_node:
# Traverse as far left as possible.
if not current_node.left:
# Visit right child if it exists.
if current_node.right:
next_node = current_node.right
# Temporarily change link.
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# Process the node if no right child.
else:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
# Restore links to prevent loops.
if current_node:
# Check if we came from the left.
if current_node.left == temp_node:
current_node.left = None
# Check if we came from the right.
elif current_node.right == temp_node:
current_node.right = None
else:
break # We've reached the root and are done
# Traverse left node, and temporarily link.
else:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
def postorder_traversal_plain(root):
result = []
current_node = root
while current_node:
# 1. Go as far left as possible
if not current_node.left:
# 2. Then try to go right
if not current_node.right:
# 5. No right child, so we are ready to visit this node
result.append(current_node.value)
# 6. Go back to parent
temp_node = current_node
current_node = current_node.parent
# 6. Restore the link and prevent re-visiting
if current_node:
# Parent's left link needs to be reset.
if current_node.left == temp_node:
current_node.left = None
# Parent's right link needs to be reset.
elif current_node.right == temp_node:
current_node.right = None
else:
# 4. Go to the right child
next_node = current_node.right
# Temporarily update links to enable backtracking
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
# 2. Go to the left child
next_node = current_node.left
# Temporarily update links to enable backtracking
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
class BetterTreeNode:
def __init__(self, value=0, left=None, right=None, parent=None):
self.value = value
self.left = left
self.right = right
self.parent = parent
def postorder_traversal_correct(root):
result = []
current_node = root
while current_node:
# Go to left
if not current_node.left:
# If no left, try right
if not current_node.right:
# Visit the node
result.append(current_node.value)
# Restore parent link, and go back up
temp_node = current_node
current_node = current_node.parent
# Restore links.
if current_node:
# Remove left reference to prevent re-visit
if current_node.left == temp_node:
current_node.left = None
# Remove right reference to prevent re-visit
elif current_node.right == temp_node:
current_node.right = None
else:
# Go to right.
next_node = current_node.right
# Temporarily update links.
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
else:
# Go to left.
next_node = current_node.left
# Temporarily update links.
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
return result
class BinaryTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def add_left(self, value):
self.left = BinaryTree(value)
return self.left
def add_right(self, value):
self.right = BinaryTree(value)
return self.right
def postorder_traversal_with_manipulation(root):
result = []
current_node = root
while current_node:
# Go left
if current_node.left:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
# Visit right
elif current_node.right:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# Visit self
else:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
if current_node:
if current_node.left == temp_node:
current_node.left = None
elif current_node.right == temp_node:
current_node.right = None
else:
break
return result
class BTNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.parent = None
def postorder_traversal_modified_english(root):
result = []
current_node = root
while current_node:
# 2. Go as far left as possible, setting links.
if current_node.left:
next_node = current_node.left
current_node.left = current_node
current_node.parent = current_node
current_node = next_node
# 3. If no left child, check right child.
elif current_node.right:
next_node = current_node.right
current_node.right = current_node
current_node.parent = current_node
current_node = next_node
# 5. No children, visit node and go back to parent.
else:
result.append(current_node.value)
temp_node = current_node
current_node = current_node.parent
# 6. Restore link and prevent revisiting.
if current_node:
# Restore the left link.
if current_node.left == temp_node:
current_node.left = None
# Restore the right link.
elif current_node.right == temp_node:
current_node.right = None
# Reached the root after processing, done.
else:
break
return resultBig(O) Analysis
Time Complexity
O(n) – The algorithm traverses the binary tree, visiting each node a constant number of times. While the while loop might appear complex, the key is that each 'parent' link modification and subsequent traversal either moves down the tree or back up. Each edge is visited and modified at most a small constant number of times. Because the number of edges in a binary tree is at most n-1, where n is the number of nodes, the algorithm performs a constant amount of work on each node and edge, thus being linear relative to the size of the tree, O(n).
Space Complexity
O(1) – The algorithm modifies the existing tree structure by temporarily changing the 'right' pointers to point to the parent nodes and sometimes sets the 'left' pointer to null. This manipulation is done in-place, meaning no additional data structures that scale with the input size N (where N is the number of nodes in the tree) are created. The algorithm uses a constant amount of extra space for variables to keep track of the current node and its parent, irrespective of the tree's size. Therefore, the auxiliary space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or Empty Tree | Return an empty list immediately as there are no nodes to traverse. |
| Single Node Tree | Return a list containing only the value of the root node. |
| Tree with only left children (skewed left) | The recursive calls should correctly traverse down the left side before returning. |
| Tree with only right children (skewed right) | The recursive calls should correctly traverse down the right side before returning. |
| Deeply nested tree (recursion depth concerns) | Iterative solution avoids stack overflow errors associated with recursion. |
| Tree with duplicate values | Postorder traversal should correctly handle nodes with duplicate values regardless of placement. |
| Very large tree (memory constraints) | Iterative solutions are generally more memory efficient compared to recursive calls. |
| Tree with negative node values | Negative values don't affect the traversal order and should be handled without modifications. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
