# binary-tree-traversals

Runnable companion for the ankurm.com article
[Binary Tree Traversals in Java: Inorder, Preorder, Postorder and Level Order (Recursive and Iterative)](https://ankurm.com/binary-tree-traversal-java-inorder-preorder-postorder-level-order/).

Recursive and iterative inorder, preorder and postorder (two-stack and one-stack), Morris traversal,
level order (plain, by level, zigzag), height, diameter (naive O(n^2) vs one pass, with counted node
visits), tree construction from traversals, and a `StackOverflowError` demo on a deep skewed tree.

| Component | Version | Verified against |
|---|---|---|
| JDK | 25.0.5+8 (Temurin, LTS) | `java -version` |
| JUnit | 6.1.3 | `maven-metadata.xml` on Maven Central (same as the sibling modules) |
| Maven | 3.9.11 | `mvn -version` |

```bash
export JAVA_HOME=/path/to/jdk-25 && export PATH="$JAVA_HOME/bin:$PATH"
cd binary-tree-traversals
mvn test                 # 15 tests; rewrites output/01-11
./scripts/run-all.sh     # also regenerates output/12-14 (StackOverflowError depth at three -Xss sizes)
```

| Source (`src/main/java/com/ankurm/interviewlab/bintree/`) | What it is |
|---|---|
| `TreeNode`, `Trees` | node class; sample tree, random/skewed/perfect/BST builders, build from inorder+preorder or inorder+postorder |
| `RecursiveTraversals` | the three textbook recursive orders |
| `IterativeTraversals` | explicit-stack inorder/preorder/postorder, Morris in/pre-order, `StepListener` hook for the step tables |
| `LevelOrder` | queue BFS, by-level grouping, zigzag |
| `TreeMetrics` | counts, height, diameter (naive and one pass, with visit counters) |
| `DeepRecursionDemo` | 1,000,000-node skewed tree: recursion overflows, iteration does not |

`output/12` to `output/14` are measurements: the overflow depth depends on the machine, the JVM and
`-Xss`, so they are not asserted. Everything else is asserted by the tests that write it.