# Binary Tree Traversal in LeetCode: Inorder, Preorder, and Postorder Explained > Master binary tree traversal: inorder preorder postorder. LeetCodeAnimation explains iterative stack solutions. Solve tree problems efficiently. - Repository: [吴师兄学算法/LeetCodeAnimation](https://github.com/MisterBooo/LeetCodeAnimation) - Tags: tutorial - Published: 2026-03-01 --- **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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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. ```java class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class InorderSolution { public List inorderTraversal(TreeNode root) { List list = new ArrayList<>(); Stack 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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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. ```java class PreorderSolution { public List preorderTraversal(TreeNode root) { List list = new LinkedList<>(); if (root == null) return list; Stack 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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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. ```java class PostorderSolution { public List postorderTraversal(TreeNode root) { List res = new ArrayList<>(); if (root == null) return res; Stack 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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/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.