java-interview-lab/binary-tree-traversals/README.md

binary-tree-traversals

Runnable companion for the ankurm.com article Binary Tree Traversals in Java: Inorder, Preorder, Postorder and Level Order (Recursive and Iterative).

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

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.