Below is a *very* gentle explanation of how our **iterative** tree traversals work using an `ArrayDeque`, which is basically a *double-ended queue* (pronounced like “deck”). Think of a **deque** as a long line of items, where you can add or remove items from both the front and the back.
---
## 1. Why do we need to switch from recursion to iteration?
When your **inorder**, **preorder**, or **postorder** traversal is **recursive**, it’s basically saying:
> “I will call myself again for the left child, then do something, then call myself again for the right child.”
Behind the scenes, every recursive call uses something called the *call stack*, which can run out of space if your tree is really big or extremely unbalanced. That’s called a **stack overflow** (not to be confused with the website name!).
By using an **iterative** approach, we don’t keep calling ourselves over and over. Instead, **we manage our own to-do list** (which is often a stack or queue data structure in memory), so we don’t rely on function calls piling up.
---
## 2. **inOrder()** using a stack (with `ArrayDeque`)
*Recap:* In *inorder* traversal, we visit:
1. *left* subtree,
2. *current node*,
3. *right* subtree.
### The code snippet
```java
public List<E> inOrder() {
List<E> list = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
Node curr = root;
while (curr != null || !stack.isEmpty()) {
// 1. Go as far left as possible
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
// 2. Pop from the stack
curr = stack.pop();
list.add(curr.value);
// 3. Switch to the right subtree
curr = curr.right;
}
return list;
}
```
### How it works in simple terms
1. **“Go as far left as possible”**: We keep **pushing** (i.e., adding to the top of) the stack every node we see while walking left. This is like collecting all the left children so we remember them.
2. **When there’s no more left**, we **pop** from the stack. That gives us the *leftmost node*, i.e., the next node in our inorder sequence. We then “record” it in `list.add(curr.value)`.
3. We **move to the right** subtree of that node, because that’s the next place in an inorder traversal. Now we might have more nodes to go left from again, so we repeat.
**Intuition**: The stack is letting us “pause” whenever we want to go left, so we can come back and pick up where we left off. If you imagine exploring a maze, every time you walk down a left path, you drop a breadcrumb on the ground (pushing to the stack). When you can’t go further, you pick up the last breadcrumb (pop from the stack), see where you were, and move on.
---
## 3. **preOrder()** using a stack (with `ArrayDeque`)
*Recap:* In *preorder* traversal, we visit:
1. *current node*,
2. *left* subtree,
3. *right* subtree.
### The code snippet
```java
public List<E> preOrder() {
List<E> list = new ArrayList<>();
if (root == null) return list;
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
list.add(node.value);
// push right, then left
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
```
### How it works in simple terms
1. We put the *root* in the stack first.
2. We pop from the stack (this is always the node we want to *visit next*).
3. We process it (add to our `list`).
4. Then we push its right child, and then left child, onto the stack. The reason we push *right first* is so that **left** is **on top** of the stack. LIFO (Last In, First Out) means we see *left* next.
5. We do that until there’s no node left in the stack.
**Intuition**: This is like reading from a pile of papers: we always pick up the top piece, read it, and then if it says “check left child and check right child,” we put those on the top of the pile. Because we do right first, we end up reading the left piece next.
---
## 4. **postOrder()** using *two* stacks (with `ArrayDeque`)
*Recap:* In *postorder* traversal, we visit:
1. *left* subtree,
2. *right* subtree,
3. *current node*.
### The code snippet
```java
public List<E> postOrder() {
List<E> list = new ArrayList<>();
if (root == null) return list;
Deque<Node> stack1 = new ArrayDeque<>();
Deque<Node> stack2 = new ArrayDeque<>();
stack1.push(root);
// Phase 1:
while (!stack1.isEmpty()) {
Node node = stack1.pop();
stack2.push(node);
if (node.left != null) stack1.push(node.left);
if (node.right != null) stack1.push(node.right);
}
// Phase 2:
while (!stack2.isEmpty()) {
list.add(stack2.pop().value);
}
return list;
}
```
### How it works in simple terms
- We have **two stacks**: `stack1` and `stack2`.
- **Phase 1**: We pop a node from `stack1`, then *push* it onto `stack2`. Meanwhile, we push its *left* and *right* children into `stack1`.
- This step basically **reverses** the usual “preorder” that we do. By the time `stack1` is empty, `stack2` has nodes in something close to reverse *postorder*.
- **Phase 2**: We pop everything from `stack2` and add to our `list`. Because they’re in reverse postorder in `stack2`, popping them gives us the correct postorder.
**Intuition**: We add root to `stack1`. Then we repeatedly pop from `stack1`, push it to `stack2`, and push its children into `stack1`. Ultimately, the order in `stack2` ends up reversed from how we want them in postorder. Popping them from `stack2` in the end yields the correct left→right→node order.
---
## 5. Why do we use `ArrayDeque` for these stacks/queues?
- **`ArrayDeque`** is basically an array that can grow from both ends. It’s very efficient at adding and removing from the top/bottom without extra overhead.
- A **stack** is usually a LIFO structure (Last In, First Out). We use the **“push”** and **“pop”** methods on an `ArrayDeque` to do that. The top of the stack is one end of the deque.
- A **queue** is usually FIFO (First In, First Out). We use **“offer”** and **“poll”** to enqueue and dequeue from the opposite ends.
To summarize:
- For **stack**-like behavior, we use `push()` and `pop()`.
- For **queue**-like behavior, we use `offer()` and `poll()`.
`ArrayDeque` is a flexible, modern choice in Java because:
1. It isn’t synchronized (which is fine for single-threaded code!). That makes it faster than something like `Stack` (the old class) or a *synchronized* structure.
2. It doesn’t have the overhead of linked nodes, like `LinkedList`. So it’s usually faster for quick operations.
---
## The Big Picture
By replacing recursion with these **iterative** methods, our code:
1. *Avoids* putting too many nested function calls on the JVM call stack.
2. *Explicitly* manages the traversal order using a data structure (`ArrayDeque`).
3. Is *efficient* because `ArrayDeque` has constant-time push/pop operations in practice.
**Like you’re 5**: You can think of a `Deque` (or stack) as a box of cards. You keep putting cards on top (pushing) while you walk the tree. When you run out of places to go, you pick up the top card (pop) and see what to do next. This gives you control over the order you visit each node of the tree, without having to keep calling yourself (which is what recursion does).