Traverse
Tree traversal always starts at the root Node.
Tree traversal involves two operations:
- visiting a Node
- iterating to visit its children
These operations can be performed in different orders.
Trees can be traversed by going straight to the leaf nodes and then walking back up..
Trees can also be traversed by visiting all Nodes at the same depth before visiting Nodes at the next greatest depth..
Traversal vs. Search
Depth-first search is a more common term than depth-first traversal. But search is just a special case of traversal. Different methods of traversal are used for use cases from deleting a tree from leaf to root (post-order), to copying a tree (pre-order), to iterating all nodes in sorted order (in-order).
Depth-First Traversal
There are three variations on depth-first traversal. All three variations use a Stack to visit Nodes in the right order.
Pre-order Traversal vists the parent before the children.
Post-order Traversal vists the children before the parent.
In-order Traversal assumes a Binary Search Tree (a Binary Tree because it assumes exactly two children and specifically a Binary Search Tree because it assumes an ordering among a node and it's left and right child), visiting the left-subtree, then the parent, and lastly the right-subtree.
Here's a link to pseudo-code which does a good job demonstrating the different orders of operations.
One advantage of depth-first traversal is that it generally uses less memory than breadth-first traversal. Though this isn't guaranteed.
Trees can have infinite depth. While depth-first traversal can be implemented either iteratively or recursively, it's important to remember that recursion is limited by stack space. 10,000 is a reasonable guideline. If your tree may extend to a depth greater than 10,000, use an iterative approach.
Breadth-First Traversal
Breadth-first traversal visits all Nodes at the same depth before visiting their children. It uses a Queue to visit Nodes in the correct order.
Breadth-first traversal is also sometimes called level-order traversal.
One advantage of breadth-first traversal is that it can always find the shortest path, while depth-first traversal sometimes cannot.
Here's pseudo-code to demonstrate the breadth-first search algorithm.