Tree Traversal

Internal

• Tree Concepts

Overview

The traversal style is named relative to the node itself. Pre-order means the node is traversed (processed first), post-order means that the node is traversed (processed) last, and in-order means that the processing is done in order from left to right: left subtree, node, right subtree.

In-Order

In-order traversal means to recursively visit the left branch, the node itself, and then the right branch (in order). In-order tree traversal can be used to print a binary search tree node keys in sorted order.

let r = root of the search tree with subtrees TL and TR
recurse of TL # by recursion/induction, prints out keys of TL in increasing order
print out r's key
recurse of TR # by recursion/induction, prints out keys of TR in increasing order

The running time is O(n).

Pre-Order

Pre-order tree traversal means to first visit (process) the current node, then branches, starting with the left branch and continuing with the right branch.