## Interview Question

## Interview Answer

3 Answers

Essentially the queue should be of a maximum length of the second last level of the tree.

The last level of a balanced tree will have n/2 nodes - where n is total number of leaf nodes

##include <stdint.h>

#include <stdlib.h>

#include <stdio.h>

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 = 1<<level;

// start at the first (leftmost) node in the level

current = 0;

while (current < level_nodes) {

// 'traversal' is the mask used to convert the

// 'current' counter into a sequence of left-right

// commands. For instance, if we want the 3rd node

// (current == 2) on level 3 (8 total nodes), in

// binary, current is 010. Traversal will start as

// 100. 010 & 100 == 0, so we go left at first and

// shift traversal right. 010 & 010 != 0, so we go

// right, and shift again. 010 & 001 == 0, so we go

// left. Once traversal is 000, we are done and we

// have found the node.

traversal = 1<<(level - 1);

path = root;

while (traversal) {

if (current & traversal) {

path = path->right;

}

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;

}

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

1+O^1+O^2..or O( | E | + | V | ) since every vertex and every edge will be explored in the worst case

Jan 21, 2011