Tree traversal

There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order.

As a tree is a self-referential (recursively defined) data structure, traversal can be defined by recursion or, more subtly, corecursion, in a natural and clear fashion; in these cases the deferred nodes are stored implicitly in the call stack.

Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue, including corecursively.

No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely.

To traverse arbitrary trees (not necessarily binary trees) with depth-first search, perform the following operations at each node: Depending on the problem at hand, pre-order, post-order, and especially one of the number of subtrees − 1 in-order operations may be optional.

For example, when inserting into a ternary tree, a pre-order operation is performed by comparing items.

In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands.

Post-order traversal can generate a postfix representation (Reverse Polish notation) of a binary tree.

If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element:[8][clarification needed] The node to be started with may have been found in the binary search tree bst by means of a standard search function, which is shown here in an implementation without parent pointers, i.e. it uses a stack for holding the ancestor pointers.

Note that the function does not use keys, which means that the sequential structure is completely recorded by the binary search tree’s edges.

With the iterative implementations we can remove the stack requirement by maintaining parent pointers in each node, or by threading the tree (next section).

A binary tree is threaded by making every left child pointer (that would otherwise be null) point to the in-order predecessor of the node (if it exists) and every right child pointer (that would otherwise be null) point to the in-order successor of the node (if it exists).

A more space-efficient approach for this type of traversal can be implemented using an iterative deepening depth-first search.

For example, given a binary tree of infinite depth, a depth-first search will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed an in-order or post-order traversal will never visit any nodes, as it has not reached a leaf (and in fact never will).

By contrast, a breadth-first search will never reach the grandchildren, as it seeks to exhaust the children first.

The nodes are thus in a one-to-one correspondence with finite (possibly empty) sequences of positive numbers, which are countable and can be placed in order first by sum of entries, and then by lexicographic order within a given sum (only finitely many sequences sum to a given value, so all entries are reached—formally there are a finite number of compositions of a given natural number, specifically 2n−1 compositions of n ≥ 1), which gives a traversal.

Thus at each step one can either go down (append a (, 1) to the end) or go right (add one to the last number) (except the root, which is extra and can only go down), which shows the correspondence between the infinite binary tree and the above numbering; the sum of the entries (minus one) corresponds to the distance from the root, which agrees with the 2n−1 nodes at depth n − 1 in the infinite binary tree (2 corresponds to binary).