34 lines
1.9 KiB
Markdown
34 lines
1.9 KiB
Markdown
# 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.
|