Tree traversal: Difference between revisions

Revision as of 11:21, 23 August 2023

Revision as of 16:17, 8 September 2023

Line 299:

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^''n''−1 compositions of {{nowrap|1=''n'' ≥ 1}}), which gives a traversal. Explicitly:

# ()