Binary Tree Traversal in LeetCode: Inorder, Preorder, and Postorder Explained

Binary tree traversal problems require visiting every node exactly once in a specific order—left-root-right for inorder, root-left-right for preorder, and left-right-root for postorder—and the LeetCodeAnimation repository solves each iteratively using a stack to simulate recursion.

The LeetCodeAnimation repository provides visual, code-driven explanations for classic algorithmic challenges, including the three fundamental binary tree traversal patterns. Each solution pairs a Java implementation with frame-by-frame animations to demonstrate how iterative stack manipulation replaces recursive calls. This guide extracts the exact strategies, file paths, and working code from the repository’s articles on LeetCode 94, 144, and 145.

Understanding Binary Tree Traversal Patterns

Binary tree traversal defines the order in which you visit each node exactly once. The three classic approaches differ only in when you process the current node relative to its children.

Inorder traversal visits nodes in left → root → right order. This sequence is particularly useful for binary search trees, where it retrieves values in ascending order.

Preorder traversal processes nodes in root → left → right order. This pattern is ideal for cloning trees or serializing structure because you capture parent nodes before children.

Postorder traversal follows left → right → root order. This approach is essential when you need to delete nodes or calculate bottom-up properties, as children are fully processed before their parent.

Inorder Traversal (LeetCode 94)

Algorithm Strategy

The iterative solution for binary tree inorder traversal uses a stack to simulate the recursive call stack. The algorithm maintains a pointer to the current node and repeatedly pushes left children onto the stack until reaching a leaf. When no left child remains, it pops the stack to visit the node, records the value, then moves to the right child to continue the pattern.

This approach guarantees left → root → right ordering because every node is processed only after its entire left subtree has been exhausted and popped from the stack.

Implementation Details

The complete logic resides in 0094-Binary-Tree-Inorder-Traversal/Article/0094-Binary-Tree-Inorder-Traversal.md. The Java implementation uses a while loop that continues until both the current pointer is null and the stack is empty.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class InorderSolution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }
}

Time complexity is O(N) where N is the number of nodes, and space complexity is O(H) where H is the tree height, bounded by O(N) in the worst case of a skewed tree.

Preorder Traversal (LeetCode 144)

Algorithm Strategy

The binary tree preorder traversal iterative solution also relies on a stack, but with a critical ordering twist: because the stack is LIFO (last-in-first-out), you must push the right child before the left child. This ensures that when you pop the stack, you process the left child first, maintaining the required root → left → right sequence.

The algorithm initializes by pushing the root onto the stack, then enters a loop that pops the top node, records its value, and pushes its children (right first, then left) until the stack empties.

Implementation Details

The full explanation and code are located in 0144-Binary-Tree-Preorder-Traversal/Article/0144-Binary-Tree-Preorder-Traversal.md. The Java implementation uses a LinkedList for the result to allow efficient insertion, though an ArrayList works equally well for append-only operations.

class PreorderSolution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            root = stack.pop();
            list.add(root.val);
            if (root.right != null) stack.push(root.right);
            if (root.left != null)  stack.push(root.left);
        }
        return list;
    }
}

Time complexity remains O(N) and space complexity is O(H), with H being the height of the tree.

Postorder Traversal (LeetCode 145)

Algorithm Strategy

The binary tree postorder traversal presents the greatest challenge for iterative implementation because you must process children before their parent (left → right → root). The solution in the LeetCodeAnimation repository uses a clever trick: it builds the result list in reverse order by prepending each visited node to the front of the list.

The algorithm pushes the root onto a stack, then repeatedly pops a node, pushes its left child first, then its right child, and inserts the node’s value at the beginning of the result list. Because children are explored left-then-right but values are prepended to the result, the final sequence becomes left-right-root.

Implementation Details

The complete walkthrough is available in 0145-Binary-Tree-Postorder-Traversal/Article/0145-Binary-Tree-Postorder-Traversal.md. The Java code uses res.add(0, node.val) to prepend values, which is O(N) per operation in an ArrayList, making the overall complexity O(N²) for that specific implementation. For production use, a LinkedList with addFirst or reversing an ArrayList at the end would be more efficient, but the repository’s educational implementation prioritizes clarity over micro-optimization.

class PostorderSolution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null)  stack.push(node.left);
            if (node.right != null) stack.push(node.right);
            res.add(0, node.val);   // prepend to achieve left-right-root order
        }
        return res;
    }
}

Time complexity is O(N) (amortized, despite the prepend cost in the educational version) and space complexity is O(H).

Summary

• Binary tree traversal problems on LeetCode (94, 144, 145) are solved iteratively in the LeetCodeAnimation repository using a stack to simulate recursion.
• Inorder traversal (0094-Binary-Tree-Inorder-Traversal/Article/0094-Binary-Tree-Inorder-Traversal.md) processes left subtree, current node, then right subtree by pushing left children until null, then popping to visit.
• Preorder traversal (0144-Binary-Tree-Preorder-Traversal/Article/0144-Binary-Tree-Preorder-Traversal.md) processes root, left, then right by pushing right child before left onto the stack.
• Postorder traversal (0145-Binary-Tree-Postorder-Traversal/Article/0145-Binary-Tree-Postorder-Traversal.md) achieves left-right-root order by prepending node values to the result list while pushing left then right children onto the stack.
• All three implementations run in O(N) time and O(H) space, where H is the tree height.

Frequently Asked Questions

What is the difference between recursive and iterative binary tree traversal?

Recursive traversal relies on the system call stack to remember parent nodes while exploring children, resulting in concise code but risking stack overflow on deep trees. Iterative traversal explicitly manages a Stack data structure to track nodes, offering the same O(N) time complexity while using O(H) heap space instead of call stack space, making it safer for skewed trees and required by many LeetCode follow-up constraints.

Why does the preorder iterative solution push the right child before the left?

The stack is LIFO (last-in-first-out), meaning the last element pushed is the first one popped. To achieve root → left → right ordering, you must push the right child first so that the left child sits on top of the stack and gets processed next. If you pushed left first, you would process right before left, violating the preorder definition.

How does the postorder traversal achieve left-right-root order with a single stack?

The algorithm modifies the result construction rather than the traversal order. It pushes the root onto a stack, then repeatedly pops a node, pushes its left child, then its right child, and prepends the popped node’s value to the result list. Because children are explored left-to-right but values are inserted at the front of the list, the final sequence becomes left → right → root without requiring a second stack or complex state tracking.

What is the time and space complexity for these iterative traversals?

All three iterative traversals run in O(N) time where N is the number of nodes, as each node is pushed and popped from the stack exactly once. The space complexity is O(H) where H is the height of the tree, representing the maximum stack depth. In the worst case of a completely skewed tree, this becomes O(N), while for a balanced tree it is O(log N). The postorder implementation in the repository uses ArrayList.add(0, val) which is O(N) per insertion, making that specific educational implementation O(N²), though the algorithmic complexity remains O(N) if using a LinkedList or reversing at the end.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}