Iterative Postorder Traversal of a Binary Tree

Question

I was attempting to solve the Q145 on LeetCode, which basically asks you to traverse a binary tree in a postorder method.

Writing the code using recursion posed no challenge, but the iterative method took some figuring out.

While I have a solution that I think works, LeetCode isn't accepting it as the error of "Memory Limit Exceeded" comes.

Is there any way to further simplify the solution I've come up with?

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}


//*******************************************


public List<Integer> postorderTraversalIterative (TreeNode root) {


        List <Integer> list = new ArrayList<>();
        Stack <TreeNode> stack = new Stack<>();

        TreeNode currentNode = root;
        int visited = 0;

        while (!stack.isEmpty() || currentNode!=null) {

            while (currentNode!=null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            currentNode = stack.pop();

            if (currentNode.right == null) {
                list.add(currentNode.val);
            }

            else {

                if (visited==0) {
                    stack.push(currentNode);
                    visited = 1;
                }

                else {
                    list.add(currentNode.val);
                    currentNode = null;
                    visited=0;
                }
            }

            if (currentNode!=null) {
                currentNode = currentNode.right;
            }
        }

        return list;
}

The bigger else block (and the variable visited) are basically there for ensuring that nodes that have a right child do get added to the list, once the right child has been traversed.

Answer 1

Does something like this work out for you? If not, please share my mistakes so that I can work on them.

public List<Integer> postorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(0, node.val); // Add node value to the front of the list

        // Push left child first, then right child
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }

    return result;
}

For tree like this:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

Result is:

[4, 5, 2, 6, 7, 3, 1]