41.2.6.4 Level–order iterations

Level–order iteration: visit the tree level by level. Example:

5-------10----12
|        |     |
1--3--4  7--9 11
   |     |  |
   2     6  8

the order of the forwards iteration is: 5, 1, 10, 3, 7, 12, 2, 4, 6, 9, 11, 8. To do it we need a moving cursor that always “turns right” keeping the count of the level. The order of the backwards iteration is: 5, 10, 1, 12, 7, 3, 11, 9, 6, 4, 2, 8.

The implementation of the level–order iteration is particularly slow, but it has the current node as the only state. The level–order iteration is usually called “breadth–first iteration” or “breadth–first search”, that name is reserved for another implementation (see Breadth–first iterations).

The following syntactic bindings are exported by the library (vicare containers binary-search-trees). The bindings whose name is prefixed with $ are unsafe operations: they do not validate their arguments before accessing them.

Forwards iteration

Function: binary-tree-fold-level-order-forwards kons knil root

Function: $binary-tree-fold-level-order-forwards kons knil root

Like fold-left for lists, visit the nodes of a binary tree with a level–order forwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree.

Function: binary-tree-begin-level-order-forwards root

Function: $binary-tree-begin-level-order-forwards root

Perform the first step in a level–order forwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree. If the tree is empty: return #f; otherwise return an instance of <binary-node> representing the first visited node.

Function: binary-tree-step-level-order-forwards bnode

Function: $binary-tree-step-level-order-forwards bnode

Advance a level–order forwards iteration by one step starting from bnode, which must be an instance of <binary-node>. If bnode is the last in the iteration: return #f; otherwise return an instance of <binary-node> representing the next visited node.

Backwards iteration

Function: binary-tree-fold-level-order-backwards kons knil root

Function: $binary-tree-fold-level-order-backwards kons knil root

Like fold-right for lists,a visit the nodes of a binary tree with a level–order backwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree.

Function: binary-tree-begin-level-order-backwards root

Function: $binary-tree-begin-level-order-backwards root

Perform the first step in a level–order backwards iteration. The argument root must be #f to represent an empty tree or an instance of <binary-node> representing the root of a tree. If the tree is empty: return #f; otherwise return an instance of <binary-node> representing the first visited node.

Function: binary-tree-step-level-order-backwards bnode

Function: $binary-tree-step-level-order-backwards bnode

Advance a level–order backwards iteration by one step starting from bnode, which must be an instance of <binary-node>. If bnode is the last in the iteration: return #f; otherwise return an instance of <binary-node> representing the next visited node.