Traversal Algorithms

General References on BST Traversal

Non Stack-Based BST Iterators Implementation Discussions

• OLD Dominion Univ: Traversing Trees with Iterator, a C++ STL-compatible iterator for BST. Q&A teaching discussion

• Morris In-Order Traversal: Inorder Tree Traversal without Recursion or Stack

Stack-Based Iterators Implementations Discussion

• stack-based pre-, in- and post-order traversal algorithms

• Both Iterative and Recursive traversal algortihms

• Overview of statck-based Java iterators for pre-order, in-order and post-order traversal

• Carneige Mellon: Java like pre-order iterator class using a stack. Source here.

Iterative Traversals

Stack-based Iterative Traversal Algorithms

• Stack-Based Iterative Algorithmns and Iterators

Non-Stack-based Iterators and Iterative Algorithms

If the node class has a parent pointer, tree traversal can be done iteratively without recourse to a stack. Such iterators classes for in-order, pre-order and post-order recursion algorithms are discussed below.

• In-order bidirectional iterator class
• Pre-order forward iterator class
• Post-order forward iterator class