Editing Tree traversal (section)

==Infinite trees==
While traversal is usually done for trees with a finite number of nodes (and hence finite depth and finite [[branching factor]]) it can also be done for infinite trees. This is of particular interest in [[functional programming]] (particularly with [[lazy evaluation]]), as infinite data structures can often be easily defined and worked with, though they are not (strictly) evaluated, as this would take infinite time. Some finite trees are too large to represent explicitly, such as the [[game tree]] for [[chess]] or [[Go (game)|go]], and so it is useful to analyze them as if they were infinite.

A basic requirement for traversal is to visit every node eventually. For infinite trees, simple algorithms often fail this. 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 (level-order) traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse any tree with bounded branching factor.

On the other hand, given a tree of depth 2, where the root has infinitely many children, and each of these children has two children, a depth-first search will visit all nodes, as once it exhausts the grandchildren (children of children of one node), it will move on to the next (assuming it is not post-order, in which case it never reaches the root). By contrast, a breadth-first search will never reach the grandchildren, as it seeks to exhaust the children first.

A more sophisticated analysis of running time can be given via infinite [[ordinal number]]s; for example, the breadth-first search of the depth 2 tree above will take [[Ordinal number#Ordinals extend the natural numbers|ω]]·2 steps: ω for the first level, and then another ω for the second level.

Thus, simple depth-first or breadth-first searches do not traverse every infinite tree, and are not efficient on very large trees. However, hybrid methods can traverse any (countably) infinite tree, essentially via a [[Diagonal argument (disambiguation)|diagonal argument]] ("diagonal"—a combination of vertical and horizontal—corresponds to a combination of depth and breadth).

Concretely, given the infinitely branching tree of infinite depth, label the root (), the children of the root (1), (2), ..., the grandchildren (1, 1), (1, 2), ..., (2, 1), (2, 2), ..., and so on. The nodes are thus in a [[bijection|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 [[Composition (number theory)|compositions]] of a given natural number, specifically 2<sup>''n''−1</sup> compositions of {{nowrap|1=''n'' ≥ 1}}), which gives a traversal. Explicitly:

# ()
# (1)
# (1, 1) (2)
# (1, 1, 1) (1, 2) (2, 1) (3)
# (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

etc.

This can be interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first search: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the first child to the second child, from the second child to the third child, etc. 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 2<sup>''n''−1</sup> nodes at depth {{nowrap|''n'' − 1}} in the infinite binary tree (2 corresponds to binary).