Problem:
Binary Tree Postorder Traversal
Given a binary tree, return the Postorder traversal of its nodes' values.
For Example:
Given:
1
\
2
/ \
3 4
Output: [3,4,2,1]
Follow up: are you able to do it iteratively?
Solution:
Postorder traversal goes left to right, bottom to top. However when we iterate the elements, we have to go from top to bottom. The top-down and left-right iteration is close to postorder traversal, we just have to reverse the top-down to down-top. We can use a stack or LinkedList to reverse the order.
import java.util.*;
class Solution {
public static void main(String...args) {
Node root = new Node(1,null,
new Node(2, new Node(3, null, null), new Node(4, null, null))
);
postOrder(root);
System.out.println();
postOrderI(root);
System.out.println();
}
public static void postOrder(Node root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value + " ");
}
public static void postOrderI(Node root) {
LinkedList<Integer> store = new LinkedList<>();
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
store.addFirst(root.value);
if(root.left != null)
stack.push(root.left);
if(root.right != null)
stack.push(root.right);
}
for(Integer i : store) {
System.out.print(i + " ");
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
class Solution {
public static void main(String...args) {
Node root = new Node(1,null,
new Node(2, new Node(3, null, null), new Node(4, null, null))
);
postOrder(root);
System.out.println();
postOrderI(root);
System.out.println();
}
public static void postOrder(Node root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value + " ");
}
public static void postOrderI(Node root) {
LinkedList<Integer> store = new LinkedList<>();
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
store.addFirst(root.value);
if(root.left != null)
stack.push(root.left);
if(root.right != null)
stack.push(root.right);
}
for(Integer i : store) {
System.out.print(i + " ");
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time complexity O(N), space complexity O(N).
The post-order iteratively solution with only one stack is a little bit harder than the inorder/preorder solution. We still follow the same spirit: before processing a node, we first travel to the left-most node, while remembering the path, so that we can later back track. We pop out the nodes and trace back. This way, when a node is popped out, we know for sure the left side branch has been done.
Binary Tree Postorder Traversal
For in-order, pre-order and post-order, The current node needs to fulfill two purposes, the first, reaching to the right branch, the second, process the node itself.
Fortunately, in-order traversal can fulfill the two purposes at the same time -- we pop out a node from stack, process it, then get the right child, never need the current node later. For pre-order, fulfill the two purpose is easy too. We process the current node before they are pushing to the stack, when we pop the current node out of the stack, we get the right child, never need the current node later.
The code for in-order and pre-order is almost identical. The only difference is: we either process a node before they are pushing on stack (pre-order) or after they are popping out of the stack (in-order).
We do left branch -> current -> right branch.
For post-order, fulfill the two purposes is trickier. The two purposes are fulfilled at different times. We need to access the current node twice. At first visit, we use it to reach the right branch, then we process the right branch, later we pop it out from the stack to process it. The current node has to remain in the stack for a while after we use it to reach the right child.
There are techniques that can handle this trickier situation. One technique, for example, is to pop out current node, get the right child, then push it back to stack if there is a right child to process. When we done processing a node, we can tell if the processed node is the right child of the stack top node, in order to figure out if we have visited the stack top node before.
Another technique, for example, is to push the current node into the stack twice, COPYA for processing it, COPYB for reaching the right branch.
import java.util.*;
class Solution {
public static void main(String...args) {
Node root = new Node(1, new Node(5, new Node(9, null, null), null),
new Node(2, new Node(3, null, null), new Node(4, null, new Node(7, null, null)))
);
postOrder(root);
System.out.println("recursive solution");
postOrderK(root);
System.out.println("iterate solution, conditionally push current node back to stack");
postOrderI(root);
System.out.println("iterate solution, push current node twice to stack");
postOrderL(root);
System.out.println("iterate solution, with the aid of another stack");
}
public static void postOrder(Node root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value + " ");
}
public static void postOrderK(Node root) {
Stack<Node> stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
Node lastNode = null;
while(!stack.isEmpty()) {
root = stack.pop();
if(root.right == lastNode) { //right child has been done?
System.out.print(root.value + " "); //yes, now time to process current node.
lastNode = root; //remember this for next node
continue;
}
//no, right child has not been procssed, time to process the right child node
Node t = root.right;
if(t!=null) { //has right child?
stack.push(root); //yes, have to process right child first
while(t != null) {
stack.push(t);
t = t.left;
}
} else {
System.out.print(root.value + " "); //no right child, time to process current node.
lastNode = root; //remember this for next node
}
}
}
public static void postOrderI(Node root) {
Stack<Node> stack = new Stack<>();
while(true) {
while(root != null) { //null means no right child or current node proessed
stack.push(root); //COPYA, use this to process current node
stack.push(root); //COPYB, use this to check the right child of the current node
root = root.left; //travel and push nodes till reaching the left-most node (same spirit as inorder and preorder traversal).
}
if(stack.isEmpty()) return; //just processed the root
root = stack.pop(); //if we pop this node out, that means the left side branch has been processed.
//time to process right branch and the current node
if(!stack.isEmpty() && root == stack.peek()) { //have we checked the right child already? Since we are handling COPYB, so not yet
root = root.right; //before process the current node, process right branch first (right child could be null)
} else { //have we checked the right child already? Since we are handling COPYA, so yes
System.out.print(root.value + " "); //because both left and right children are done, we can now process current node
root = null; //mark current node processed
}
}
}
public static void postOrderL(Node root) {
Stack<Node> store = new Stack<>();
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
root = stack.pop();
store.push(root);
if(root.left != null)
stack.push(root.left);
if(root.right != null)
stack.push(root.right);
}
while(!store.isEmpty()) {
System.out.print(store.pop().value + " ");
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
