Facebook

www.facebook.com
www.facebook.com

## Interview Question

Engineering Intern Interview

# How would you print a large, balanced degree-bound tree in

breadth first order, using only O(1) space?
Answer

## Interview Answer

3 Answers

0

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

Anonymous on Jan 21, 2011
0

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

deveffort on Jan 25, 2011
0

##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;
}

Anonymous on Jun 23, 2014

## Add Answers or Comments

To comment on this, Sign In or Sign Up.