##include #include #include struct node { int value; struct node *left; struct node *right; }; /** * An effectively O(1) (constant) space BFS traversal of a * tree, at the cost of O(N log N) time. However, it is * impossible to have a truly constant space algorithm for * this purpose; in this case, the space is technically * O(log N)... except that because we only use 1 extra bit * per doubling of N we can visit up to 2^63 nodes using less * than 64 bytes of space. * * There is also a fairly easy optimization that can be made * for a space/time tradeoff (while maintaining constant * space). For instance, at the cost of a pointer, you can * maintain a pointer to the parent node of the node on * the current level you're checking. For every right child, * you can then skip the traversal from the root, saving you * 50% of your time for a constant 8 bytes (on a 64 bit system) * of memory. Similarly, you can cache two levels of parents, * saving you 75% of full traversals. * * At the logical extension of this you can just keep 64 layers * of parent pointers, at which point you're using a (constant) * half a kilobyte of RAM, and cutting down on the traversal cost * by a pretty dramatic amount. */ uint64_t traverse(const struct node* root, void(*handler)(const struct node*)) { int level; int next_level_found; uint64_t current; uint64_t traversal; uint64_t visited = 0; uint64_t level_nodes; const struct node *path; if (!root) { goto exit; } handler(root); visited++; next_level_found = (root->left || root->right); while (next_level_found) { // start on the next level (levels are 0 indexed) level++; // we do not know if a next level exists yet next_level_found = 0; // each level has 2^level nodes in total level_nodes = 1right; } else { path = path->left; } if (!path) { break; } traversal >>= 1; } if (path) { handler(path); visited++; // if a node in the current level has children, // we will need to hit the next level to find them // once we finish this level if (path->left || path ->right) { next_level_found = 1; } } } current++; } } exit: return visited; }