Binary Tree Postorder Traversal

1. Define a helper function, say traverse(node, resultList).
2. The base case for the recursion is if the node is null, in which case we simply return.
3. If the node is not null, recursively call the traverse function for the left child: traverse(node.left, resultList).
4. After the left subtree has been fully explored, recursively call the traverse function for the right child: traverse(node.right, resultList).
5. Finally, after both left and right subtrees have been traversed, add the value of the current node to the resultList: resultList.add(node.val).
6. The main function initializes an empty list and calls the helper function with the root of the tree.

This approach leverages the call stack to keep track of the nodes. When a function is called for a node, it first makes a recursive call for its left child. This process continues until a null node is reached. Then, the execution unwinds, and a recursive call is made for the right child. Only after both the left and right recursive calls for a node have returned, is the node's value added to the result list. This naturally ensures the 'Left -> Right -> Root' order.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<Integer> postorderTraversal(TreeNode root) {18        List<Integer> result = new ArrayList<>();19        traverse(root, result);20        return result;21    }22 23    private void traverse(TreeNode node, List<Integer> result) {24        if (node == null) {25            return;26        }27        // 1. Traverse left subtree28        traverse(node.left, result);29        // 2. Traverse right subtree30        traverse(node.right, result);31        // 3. Visit the root32        result.add(node.val);33    }34}

1. If the root is null, return an empty list.
2. Create two stacks, stack1 and stack2.
3. Push the root node onto stack1.
4. Loop as long as stack1 is not empty: a. Pop a node from stack1. b. Push this popped node onto stack2. c. If the node's left child exists, push it onto stack1. d. If the node's right child exists, push it onto stack1.
5. The order of pushing left then right children onto stack1 results in stack2 storing nodes in the order: Root, Right, Left.
6. Create a result list.
7. Pop all nodes from stack2 and add their values to the result list. This reverses the Root -> Right -> Left order to Left -> Right -> Root.
8. Return the result list.

We use a first stack (stack1) to perform a custom traversal. We start by pushing the root. In a loop, we pop a node, push it to a second stack (stack2), and then push its left and right children (if they exist) onto stack1. By pushing the left child before the right child, the right child will be processed first, leading to a Root -> Right -> Left processing order. The stack2 will store the nodes in this sequence. Finally, we pop all elements from stack2 into our result list, which effectively reverses the sequence to the desired postorder traversal.

1class Solution {2    public List<Integer> postorderTraversal(TreeNode root) {3        LinkedList<Integer> result = new LinkedList<>();4        if (root == null) {5            return result;6        }7 8        Stack<TreeNode> stack = new Stack<>();9        stack.push(root);10 11        while (!stack.isEmpty()) {12            TreeNode node = stack.pop();13            // Add to the front of the list, which is equivalent to reversing14            result.addFirst(node.val);15 16            // Push left child first, so right child is processed first17            if (node.left != null) {18                stack.push(node.left);19            }20            if (node.right != null) {21                stack.push(node.right);22            }23        }24        return result;25    }26}27// Note: The above code is an optimization of the two-stack approach.28// It uses one stack and a LinkedList, adding elements to the front29// which achieves the reversal without a second stack explicitly.30// A literal two-stack implementation would be:31/*32Stack<TreeNode> s1 = new Stack<>();33Stack<TreeNode> s2 = new Stack<>();34s1.push(root);35while(!s1.isEmpty()){36    TreeNode node = s1.pop();37    s2.push(node);38    if(node.left != null) s1.push(node.left);39    if(node.right != null) s1.push(node.right);40}41List<Integer> result = new ArrayList<>();42while(!s2.isEmpty()){43    result.add(s2.pop().val);44}45return result;46*/

1. Initialize an empty result list, an empty stack, and set current to root.
2. Use a lastVisited node pointer, initialized to null.
3. Loop while current is not null or the stack is not empty.
4. Inside the loop: a. While current is not null, push it onto the stack and move to its left child (current = current.left). b. When current becomes null, peek at the node on top of the stack (peekNode). c. Check if peekNode has a right child and if that right child has not been visited yet (peekNode.right != null && peekNode.right != lastVisited). d. If it does, it means we need to traverse the right subtree. Set current = peekNode.right and continue the loop. e. Otherwise (no right child, or right child already visited), it's time to visit peekNode. Pop it from the stack, add its value to result, and update lastVisited = peekNode.

The algorithm traverses down the leftmost path of the tree, pushing each node onto a stack. When it can't go left anymore, it peeks at the stack's top node. It then checks if this node has a right subtree that hasn't been visited yet. If so, it switches to traversing that right subtree. If not (either no right child or the right child has already been visited and processed), it means both children have been dealt with, so it's time to 'visit' the node itself. The node is popped, its value is added to the result, and it's marked as the lastVisited node. This lastVisited check is crucial to prevent getting into an infinite loop by repeatedly trying to visit the same right subtree.

1class Solution {2    public List<Integer> postorderTraversal(TreeNode root) {3        List<Integer> result = new ArrayList<>();4        if (root == null) {5            return result;6        }7 8        Stack<TreeNode> stack = new Stack<>();9        TreeNode current = root;10        TreeNode lastVisited = null;11 12        while (current != null || !stack.isEmpty()) {13            while (current != null) {14                stack.push(current);15                current = current.left;16            }17 18            TreeNode peekNode = stack.peek();19            // If right child exists and hasn't been visited yet20            if (peekNode.right != null && peekNode.right != lastVisited) {21                current = peekNode.right;22            } else {23                // Visit the node24                stack.pop();25                result.add(peekNode.val);26                lastVisited = peekNode;27            }28        }29        return result;30    }31}

1. Create an empty list result.
2. Set current to root.
3. While current is not null: a. If current.right is null, it means there's no right subtree to visit before the left. Add current.val to the result and move left (current = current.left). b. If current.right is not null, find the inorder predecessor of current in its right subtree. This is the leftmost node of the right subtree (predecessor). c. If predecessor.left is null (no thread exists), add current.val to result, create a thread from predecessor back to current (predecessor.left = current), and move right (current = current.right). d. If predecessor.left points to current (thread exists), it means we have finished the traversal of current's right subtree. Remove the thread (predecessor.left = null) and move left (current = current.left).
4. After the loop, the result list contains the nodes in Root -> Right -> Left order.
5. Reverse the result list to get the final postorder traversal.
6. Return the reversed list.

The core idea is to adapt the Morris traversal logic. Instead of linking the inorder predecessor to the current node for an inorder traversal, we adapt it for a Root -> Right -> Left traversal. We traverse the tree, and for each node, we check its right child. If no right child exists, we process the node and move to the left child. If a right child exists, we find its inorder predecessor (the leftmost node in the right subtree). We then create a temporary link (thread) from this predecessor back to the current node. This thread allows us to return to the current node after visiting its right subtree. By carefully adding nodes to our result list before traversing the right subtree and then reversing the entire list at the end, we achieve the postorder sequence. This method cleverly uses the tree's own null pointers to store the path, thus achieving O(1) space complexity.

1class Solution {2    public List<Integer> postorderTraversal(TreeNode root) {3        LinkedList<Integer> result = new LinkedList<>();4        TreeNode current = root;5        while (current != null) {6            if (current.right == null) {7                result.addFirst(current.val);8                current = current.left;9            } else {10                TreeNode predecessor = current.right;11                while (predecessor.left != null && predecessor.left != current) {12                    predecessor = predecessor.left;13                }14 15                if (predecessor.left == null) {16                    result.addFirst(current.val);17                    predecessor.left = current; // Create thread18                    current = current.right;19                } else {20                    predecessor.left = null; // Remove thread21                    current = current.left;22                }23            }24        }25        return result;26    }27}