LeetCode 144: Binary Tree Preorder Traversal

Explanation

To perform a preorder traversal of a binary tree iteratively, we can use a stack to simulate the recursive call stack. The preorder traversal visits the root node first, then recursively visits the left subtree, and finally recursively visits the right subtree.

Here's the step-by-step algorithm:

1. Initialize an empty stack and a list to store the result.
2. Push the root node onto the stack.
3. While the stack is not empty, pop a node from the stack.
4. Add the node's value to the result list.
5. If the node has a right child, push the right child onto the stack.
6. If the node has a left child, push the left child onto the stack.
7. Repeat steps 3-6 until the stack is empty.

Time complexity: O(n) - where n is the number of nodes in the tree. Space complexity: O(n) - in the worst-case scenario where the binary tree is skewed, the stack can hold all the nodes.

public List<Integer> preorderTraversal(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(node.val);
        
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    
    return result;
}