Tree traversal with backtracking in constant time

A system comprising:

• a processor that is configured to:
• traverse a tree;
• during the traverse, maintain a bit trail variable and a current key variable in registers associated with the processor, the bit trail variable including a first plurality of bits indicating tree levels on which a node has been postponed along a path from a root of the tree during the traversing, and the current key variable including a second plurality of bits indicating a number of a current node within the tree;
• and
• perform backtracking to a postponed node within the tree during the traversing, utilizing the bit trail variable and the current key variable, wherein an address of the postponed node is obtained in constant time using a perfect hash map,
• wherein the current key variable is maintained by appending a 0 bit to the first plurality of bits when a left child of a node is selected when the traversing proceeds past the node or appending a 1 bit to the first plurality of bits when a right child of the node is selected when the traversing proceeds past the node, and
• wherein the bit trail variable is maintained by appending a 0 bit when no backtracking is required when the traversing proceeds past the node or appending a 1 bit when backtracking is required when the traversing proceeds past the node.

A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, causes the processor to perform steps comprising:

• traversing a tree;
• during the traversing, maintaining a bit trail variable and a current key variable in registers associated with the processor, the bit trail variable including a first plurality of bits indicating tree levels on which a node has been postponed along a path from a root of the tree during the traversing, and the current key variable including a second plurality of bits indicating a number of a current node within the tree;
• and
• performing backtracking to a postponed node within the tree during the traversing, utilizing the bit trail variable and the current key variable, wherein an address of the postponed node is obtained in constant time using a perfect hash map,
• wherein the current key variable is maintained by appending a 0 bit to the first plurality of bits when a left child of a node is selected when the traversing proceeds past the node or appending a 1 bit to the first plurality of bits when a right child of the node is selected when the traversing proceeds past the node, and
• wherein the bit trail variable is maintained by appending a 0 bit when no backtracking is required when the traversing proceeds past the node or appending a 1 bit when backtracking is required when the traversing proceeds past the node.