Binary Search Tree Tranversal

Depth-first[edit]

See also: Depth-first search

There are three types of depth-first traversal: pre-order,^[1] in-order,^[1] and post-order.^[1] For a binary tree, they are defined as operations recursively at each node, starting with the root node as follows:

Pre-order[edit]

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

In-order (symmetric)[edit]

1. Traverse the left subtree.
2. Visit root.
3. Traverse the right subtree.

Post-order[edit]

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

Breadth-first[edit]

See also: Breadth-first search

Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level.