NVIDIA Corporation
Tree traversal with backtracking in constant time

Abstract:

A method, computer readable medium, and system are disclosed for performing tree traversal with backtracking in constant time. The method includes the steps of traversing a tree, maintaining a bit trail variable and a current key variable during the traversing, where the bit trail variable includes a first plurality of bits indicating tree levels on which a node has been postponed along a path from the root of the tree during the traversing, and the current key variable includes a second plurality of bits indicating a number of a current node within the tree, and performing backtracking within the tree during the traversing, utilizing the bit trail variable and the current key variable.