https://en.wikipedia.org/wiki/Tree_traversal

Pre-order Traversal

1. Check if the current node is empty / null
2. Display the data part of the root (current node)
3. Traverse the left subtree by recursively calling the pre-order function
4. Traverse the right subtree by recursively calling the pre-order function

Recursion Implementation

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();

        dfsHelper(root, result);

        return result;
    }

    private void dfsHelper(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        dfsHelper(root.left, result);
        dfsHelper(root.right, result);
    }
}

Iterative solution: stack

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) return result;

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

        while (!stack.isEmpty()) {
            TreeNode currNode = stack.pop();

            result.add(currNode.val);

            if (currNode.right != null) stack.push(currNode.right);
            if (currNode.left != null) stack.push(currNode.left);
        }

        return result;
    }
}

In-order Traversal

left => current => right

Recursive solution

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();

        dfsHelper(root, result);

        return result;
    }

    private void dfsHelper(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        dfsHelper(root.left, result);
        result.add(root.val);
        dfsHelper(root.right, result);
    }
}

Iterative solution: stack + currRoot

be careful with not falling into the cycle of adding left nodes repeatedly

• while (node != null)
• instead of while (node.left != null)

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();

            result.add(node.val);

            node = node.right;
        }


        return result;
    }
}

Post-order Traversal

left => right => current

Recursive solution

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Postorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<>();

        dfsHelper(root, result);

        return result;
    }

    private void dfsHelper(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        dfsHelper(root.left, result);
        dfsHelper(root.right, result);
        result.add(root.val);
    }
}

Iterative solution I: stack + currRoot + parent Pointer

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Postorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode currNode = root;
        TreeNode prevNode = null;

        stack.push(root);
        while (!stack.isEmpty()) {
            currNode = stack.peek();
            if (prevNode == null || prevNode.left == currNode || prevNode.right == currNode) {//traverse down the tree
                if (currNode.left != null) {
                    stack.push(currNode.left);
                } else if (currNode.right != null) {
                    stack.push(currNode.right);
                }
            } else if (currNode.left == prevNode) {//traverse up the tree from the left
                if (currNode.right != null) {
                    stack.push(currNode.right);
                }
            } else {//prev == curr, reach leftmost node or traverse up the tree from the right
                result.add(currNode.val);
                stack.pop();
            }

            prevNode = currNode;
        }

        return result;
    }
}

Iterative solution II: stack + LinkedList

addFirst method is in interface Deque<E>, so you can't declare the linked list by abstract class list

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();

        if (root == null) return result;

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

        while(!stack.isEmpty()) {
            TreeNode currNode = stack.pop();
            result.addFirst(currNode.val);

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

            if (currNode.right != null) {
                stack.push(currNode.right);
            }
        }

        return result;
    }
}