Leetcode 144. Binary Tree Postorder Traversal: Given the root of a binary tree, return the Postorder traversal of its nodes’ values.
This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.
1. Introduction
In this article, I will discuss how to traverse a Binary Tree using Postorder traversal using Recursive and Iterative (without recursion) methods.
2. Content
Below are examples of Binary Tree and their respective Postorder traversal results.
Example 1: Postorder Traversal = [4,5,2,6,7,3,1]
Example 2: Postorder Traversal = [10,4,2,7,5,8,6,3,1]
3. Postorder Traversal
Steps for Postorder traversal:
- Recursively traverse the current node’s left subtree
- Recursively traverse the current node’s right subtree
- Visit the node
The good part about recursion is that we don’t need to track the nodes in the stack. The system stack takes care of that for us. This makes our job really easy if we are implementing the traversal using recursion.
4. Postorder Traversal using Recursion
In order to save the result of traversal, we need to use ArrayList.
Below is the code for Postorder Traversal of the Binary Tree using Recursion.
public List<Integer> postorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return Collections.unmodifiableList(result);
}
private void postorder(TreeNode root, List<Integer> result) {
if(root != null) {
postorder(root.left, result);
postorder(root.right, result);
result.add(root.val);
}
}
Time Complexity:
- O(n) where n is the total number of nodes in the Binary Tree.
Space Complexity:
- O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree. Below is what a skewed tree looks like.
5. Postorder Traversal using Iteration
Postorder traversal using Iteration is a little tricky than Inorder or Preorder. In a Postorder traversal, we will traverse the root node last. As we have to traverse the right node immediately after the left node, we need to do two things:
1. Check if the peek stack element has the right node.
2. Check if this peek stack element isn’t visited.
If the peek stack element doesn’t have the right node, then visit that node else explore the right subtree.
We just need to keep track of the last visited node so we know whether the peek element’s right subtree is explored or not.
You will need to debug this code a few times to get a hang of it.
Below is the code to traverse a Binary Tree using Postorder Traversal.
public List<Integer> postorderTraversalIterativeBetter(TreeNode root) {
if(root == null) return Collections.emptyList();
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode lastVisited = null;
TreeNode curr = root;
while(curr != null || !stack.isEmpty()) {
if(curr != null) {
stack.push(curr);
curr = curr.left;
} else {
TreeNode peekNode = stack.peek();
// if right child exists and traversing node
// from left child, then move right
if(peekNode.right != null && lastVisited != peekNode.right) {
curr = peekNode.right;
} else {
result.add(peekNode.val);
lastVisited = stack.pop();
}
}
}
return result;
}
Time Complexity:
- O(n) where n is the total number of nodes in the Binary Tree.
Space Complexity:
- O(h) where h is the height of the tree. If the tree is skewed, then the factor h degrades to n, where n is the total number of nodes in the tree.
6. Conclusion
In this article, we saw Postorder Traversal of the Binary Tree using Recursion and Iteration.