Tree Traversal - Infinite Trees

Infinite Trees

While tree traversal is generally done for finite trees – finite number of nodes, 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. More practically, some trees are, while finite, so large as to in practice be infinite, such as the game tree for chess or go, and thus analyzing them as if they were infinite is useful – infinite trees are the limiting case of very large trees.

A basic requirement for traversal is to visit every node. For infinite trees, simple algorithms often fail this. For example, given a binary tree of infinite depth, a depth-first traversal will go down one side (by convention the left side) of the tree, never visiting the rest, and indeed if in-order or post-order 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 node has infinitely many children, and each of these children has two children, a depth-first traversal 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 traversal 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 numbers; for example, the breadth-first traversal of the depth 2 tree above will take ω·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 (diagonal – combination of vertical and horizontal – corresponds to hybrid – combination of depth and breadth).

Concretely, given the infinitely branching tree of infinite depth, label the root node the children of the root node the grandchildren and so forth. 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. Explicitly:

0: 1: (1) 2: (1,1) (2) 3: (1,1,1) (1,2) (2,1) (3) 4: (1,1,1,1) (1,1,2) (1,2,1) (1,3) (2,1,1) (2,2) (3,1) (4)

etc.

This can be alternatively interpreted as mapping the infinite depth binary tree onto this tree and then applying breadth-first traversal: replace the "down" edges connecting a parent node to its second and later children with "right" edges from the 1st child to the 2nd child, 2nd child to third child, etc. Thus at each step one can either go down (append a (,1) to the end) or go right (add 1 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 1) 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).