# Cupif-Giannini tree traversal

(algorithm)

Definition: Visit every leaf of a perfect binary tree with maximum dispersion (see note). For a tree of height n, use an n-bit "count" integer. The least significant bit of count indicates whether to go to the left or right child from the root. Each more significant bit indicates whether to go left or right. Regular binary counting generates the list of 2n paths to the leaves.

To randomly permute the order of leaf visits, choose a random n-bit "key" at the beginning. Use the xor of the key and the count to indicate which child to visit.

Note: "Dispersion" means the next leaf visited is as far from other leaves visited as possible. More formally, the next leaf has the maximum shortest path to the preceding leaf (with less importance given to be far from more distantly preceeding leaves).

It doesn't matter to the dispersion whether a 0 bit means left (and 1 means right) or 0 means right (and 1 means left). Also the initial value of count doesn't matter, as long as overflow is handled.

To picture the algorithm, consider starting with a count of 000...00, indicating going down all left branches to the first leaf. The next count is 000...01, which has a shortest path distance of 2n: from the first leaf, go up to the root, take the right branch, then down to the second leaf. The next count is 000...10. This third leaf is 2n from the immediately preceding leaf (the second one) and 2n-1 from the first leaf: up to one below the root, then down to the first leaf.

Here is pseudocode for an inefficient Cupif-Giannini tree traversal with Xor "randomization" (** is the power operator, and ^ is xor):

` visitNode(tree, nodeNumber, bitNumber) begin     if isLeaf(tree), then         print(tree.root);     else         if the bitNumber-th bit of nodeNumber is 1, then             visitNode(tree.left_subtree, nodeNumber, bitNumber+1);         else             visitNode(tree.right_subtree, nodeNumber, bitNumber+1);         endif     endif end  cupifGiannini(tree) begin     key = random();     for n = 0 to 2**height(tree)-1         visitNode(tree, n ^ key, 1);     endfor end `

Author: PEB