Problem

Given a binary tree, write an algorithm for postorder traversal.

Postorder Traversal

  1. Visit all the nodes in the left subtree
  2. Visit all the nodes in the right subtree
  3. Visit the root node
1
2
3

postorder(root->left)
postorder(root->right)
display(root->data)

Examples

Example 1:

1
2
3
4
5

   1
    \
     2
    /
   3

1
2

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

Example 2:

graph TD;
1 --- 2 & 3
2 --- 4 & 5
3 --- 6 & 7
  
1
2

Input: root = [1,2,3,4,5, 6, 7]
Output: [4, 5, 2, 6, 7, 3, 1]

Follow up

Using recursion is not allowed.

Solution

This is how the post-order traversal looks:

Method 1 - Recursion

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}
	helper(root, ans);
}

private void helper(TreeNode root, List<Integer> ans) {
	if (root == null) {
		return;
	}
	helper(root.left, ans);
	helper(root.right, ans);
	ans.add(root.val);
}

Method 2 - Using 2 Stacks

We have seen inorder and preorder traversal, but post order traversal is slightly more complex, as we have to take care of root after both left and right subtree. Postorder traversal is also non-tail recursive ( The statements execute after the recursive call).

Also, observe that postorder traversal is just reverse of preorder traversal. Lets look at example 2 above:

  • Pre-order traversal, processing left child first and then right - 1, 2, 4, 5, 3, 6, 7
  • Pre-order traversal, processing right child first and then left - 1, 3, 7, 6, 2, 5, 4
  • Post-order traversal - 4, 5, 2, 6, 7, 3, 1

So idea is follow the same technique as preorder traversal and instead of adding the answer to list, we just push it to another stack.

At the end just pop all the items from the second Stack and add them to list automatically in Last in first out (LIFO) order.

Pseudocode

  • Push root into stack1.
  • While stack1 is not empty
    • Pop the values from stack1 and push them into stack2.
    • Push the left and right child nodes of popped node into stack1.
  • Pop out all the nodes from stack2 and add to post-order traversal list.

Dry run

See the dry run below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}
	
    Stack <TreeNode> s1 = new Stack <> ();
    Stack <TreeNode> s2 = new Stack <> ();

    s1.push(root);
    
    while (!s1.isEmpty()) {
        TreeNode curr = s1.pop();
        s2.push(curr);

        if (curr.left != null) {
            s1.push(curr.left);
        }
        if (curr.right != null) {
            s1.push(curr.right);
        }
    }
    

    while (!s2.isEmpty()) {
        ans.add(s2.pop());
    }
    
    return ans;
}

Method 3 - Using 1 Stack

The key to to iterative postorder traversal is the following:

  1. The order of “Postorder” is: left child -> right child -> parent node.
  2. Find the relation between the previously visited node and the current node
  3. Use a stack to track nodes

As we go down the tree to the left, check the previously visited node. If the current node is the left or right child of the previous node, then keep going down the tree, and add left/right node to stack when applicable. When there is no children for current node, i.e., the current node is a leaf, pop it from the stack. Then the previous node become to be under the current node for next loop. You can using an example to walk through the code.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class Solution {
 public ArrayList <Integer> postorderTraversal(TreeNode root) {

    ArrayList <Integer> lst = new ArrayList <Integer> ();

    if (root == null) {
	    return lst;
    }

    Stack <TreeNode> stack = new Stack <TreeNode> ();
    stack.push(root);

    TreeNode prev = null;
    while (!stack.empty()) {
        TreeNode curr = stack.peek();

        // go down the tree.
        //check if current node is leaf, if so, process it and pop stack,
        //otherwise, keep going down
        if (prev == null || prev.left == curr || prev.right == curr) {
            //prev == null is the situation for the root node
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            } else {
                stack.pop();
                lst.add(curr.val);
            }

            //go up the tree from left node
            //need to check if there is a right child
            //if yes, push it to stack
            //otherwise, process parent and pop stack
        } else if (curr.left == prev) {
            if (curr.right != null) {
                stack.push(curr.right);
            } else {
                stack.pop();
                lst.add(curr.val);
            }

            //go up the tree from right node
            //after coming back from right node, process parent node and pop stack.
        } else if (curr.right == prev) {
            stack.pop();
            lst.add(curr.val);
        }

        prev = curr;
    }

    return lst;
}
}

Simpler code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public List<Integer> postorderTraversal(TreeNode root) {
	LinkedList<Integer> ans = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	if (root == null) return ans;
	
	stack.push(root);
	while (!stack.isEmpty()) {
		TreeNode cur = stack.pop();
		ans.addFirst(cur.val);
		if (cur.left != null) {
			stack.push(cur.left);
		}
		if (cur.right != null) {
			stack.push(cur.right);
		} 
	}
	return ans;
}

Method 4 - One Stack with Tree Modification

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public List < Integer > postorderTraversal(TreeNode root) {
    List < Integer > res = new ArrayList < > ();

    if (root == null) {
        return res;
    }

    Stack < TreeNode > stack = new Stack < TreeNode > ();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode temp = stack.peek();
        if (temp.left == null && temp.right == null) {
            TreeNode pop = stack.pop();
            res.add(pop.val);
        } else {
            if (temp.right != null) {
                stack.push(temp.right);
                temp.right = null;
            }

            if (temp.left != null) {
                stack.push(temp.left);
                temp.left = null;
            }
        }
    }

    return res;
}