Facebook Interview Question: How would you print a large, ... | Glassdoor

Interview Question

Engineering Intern Interview

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

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

Interview Answer

3 Answers


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

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


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;


    next_level_found = (root->left || root->right);

    while (next_level_found) {
        // start on the next level (levels are 0 indexed)

        // 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) {

                traversal >>= 1;

            if (path) {

                // 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;


    return visited;

Anonymous on Jun 23, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.