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 question, Sign In with Facebook or Sign Up