In this post, I will put all iterative solution of traversals (preorder, inorder, postorder) together for better understanding.

Leetcode No.94 Binary Tree Inorder Traversal
Leetcode No.144 Binary Tree Preorder Traversal
Leetcode No.145 Binary Tree Postorder Traversal

Problem Description:

Given a binary tree, return the inorder/preorder/postorder traversal of its nodes’ values.

Analysis:

First I’ll clarify these three traversal orders. Sometimes it’s easy to get confused of these three traversal orders. We can just look at the prefix: pre, in, post. This means the order of the root node in relation to left-right node pair. The relative order of left-right doesn’t change, and the prefix indicates whether the root node is before, or in between, or after the left-right pair.

preorder: root, left, right
inorder: left, right, root
postorder: left, right, root


preorder: 1 - 2 - 4 - 5 - 3 - 6 - 7
inorder: 4 - 2 - 5 - 1 - 6 - 3 - 7
postorder: 4 - 5 - 2 - 6 - 7 - 3 - 1

It’s very easy to implement using the recursive method. But it can be a bit tricky to do it iteratively. In the preorder and inorder, the ideas are similar, we use a stack to help us guide through the traversal. Except that in preorder, we only add the right nodes to the stack, and in inorder, we only add the left nodes. As for postorder, we still use a stack, except the code may seem quite counterintuitive, because we build the list in a root-right-left reversed order (which is exactly postorder), with linked-list’s addFirst() method, adding each number to the beginning of the list as we proceed. The following is the code, and I believe it takes sometime to really understand the process.

TreeTraversal.java
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
 public class TreeTraversal {

    public List<Integer> inorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            if (root.right != null) {
                root = root.right;
            }
        }
        return res;
    }

    public List<Integer> preorder(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();

        while (root != null || !stack.isEmpty()) {
            res.add(root);
            if (root.right != null) {
                stack.push(root.right);
            }
            root = root.left;

            // go to the most recent right node only when there's no left child to this node
            if (root == null && !stack.isEmpty()) {
                root = stack.pop();
            }
        }
    }

    public List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (root != null || !stack.isEmpty()) {
            root = stack.pop();
            list.addFirst(root.val);
            if (root.left != null)  stack.push(root.left);
            if (root.right != null) stack.push(root.right);
        }
    }
}

I’ll also include recursive approach here.

inorderTraversal.java
1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if (root == null) return res;
    inorder(res, root);
    return res;
}

private void inorder(List<Integer> res, TreeNode node) {        
    if (node.left != null)  inorder(res, node.left);
    res.add(node.val);
    if (node.right != null) inorder(res, node.right);
}
postorderTraversal.java
1
2
3
4
5
6
7
8
9
10
11
public List<Integer> postorderTraversal(TreeNode root) {
	if (root == null)  return new ArrayList<>();
	List<Integer> list = new ArrayList<>();
	postorder(list, root);
	return list;
}
private void postorder(List<Integer> list, TreeNode root) {
	if(root.left != null)  postorder(list, root.left);
	if(root.right != null)  postorder(list, root.right);		
	list.add(root.val);
}
preorderTraversal.java
1
2
3
4
5
6
7
8
9
10
11
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    visit(res, root);
    return res;
}
private void visit(List<Integer> list, TreeNode node) {
    list.add(node.val);
    if (node.left != null)   visit(list, node.left);
    if (node.right != null)  visit(list, node.right);
}