Python In-order Binary Tree Traversal
September 23, 2009

Comparison on a dual-core 2.00 Ghz Pentium with 2 Gig RAM
These comparisons were done in Python. Source available at the following site: details of options, figures, and source.

In-order Tree traversal options:

1. Recursion: uses the function stack space to store traversal information.

2. Stack with visited flag: requires a flag on every node, so more tree memory.

3. To reduce flag memory: method 2 but replace the node with a temporary object on entry and restore on exit.

3b. Use object recycling in 3 to reduce allocation costs.

4. Dual stack: method 3 but additional stack for flags

5. Parent pointer with next, current, and prev pointers. No stack. Tested code from someone's weblog on iterative methods.
6. Parent pointer with state-based traversal: Method 5 but store the state explicitly (i.e. going down left, going up, or going down right).
6.b. Optimization of 6 by short-circuiting loops.
Additional comparison to usage of the built in Python array class also performed. (details)

Storage costs

O(log n) additional memroy: Recursion (1) and modified stack (3, 3b, 4) require overhead on the order of the depth of the tree, so these methods are comparable.

O(n) additional memory: Visited flag (2) and parent pointer (5, 6, 6b) require additional memory on the order of the tree size, so those require relatively more memory than O(lg n) storage methods.

Computation cost

All methods are O(N) and visit each node 1 to 3 times (additional visits when coming back up from each child). Thus, the difference is in the constants and may depend on the programming language. Table of the results and graph available on a different page link.

Conclusions

Note that these measurements are influenced by the computer architecture and programming language (Python).

Overall (all): Recursion was fastest of the methods. This implies that the overhead for function calling is low relative to storing items in a list.
Iterative methods (2 through 6b): visited flag was fastest. This implies that minimizing assignments and comparisons was important. However this method uses more memory than stack methods.
Iterative methods with O(lg n) storage (3, 3b, 4): Having an auxiliary stack for storing visited flags was a little faster than swapping in a temp object to store the flag. Using memory recycling was not beneficial implying that the object allocation procedures in Python are quite efficient.
Iterative methods with O(n) storage (2, 5, 6, 6b): Storing the visited flag was faster than handling parent traversal. Using the parent flag is slower since there are overall more assignments and comparisons necessary. As usual, simple is better.
Iterative methods with parent pointer and O(1) additional storage (5, 6, 6b): Method 5 was slowest likely due to the many comparisons and assignments necessary to determine traversal state. Optimization of 6 to 6b produced marginal improvements.

So it seems recursion is the way to go. It is the simplest to code, executes quickly, and uses low additional storage (O(lg n) is the least for the methods compared.)