balanced binary tree visit with a twist

Question

Looking for an in-place O(N) algorithm which prints the node pair(while traversing the tree) like below for a given balanced binary tree:

                 a

              b     c

             d e   f g

Output: bc, de, ef, fg

Where 'a' is the root node, 'b' the left child, 'c' the right, etc. Please note the pair 'ef' in the output.

Additional info based on comments below:

1. 'node pair' is each adjacent pair at each level
2. each node can have 'parent' pointer/reference in addition to 'left' and 'right'
3. If we were to relax O(N) and in-place, are there more simple solutions (both recursive and iterative)?

Answer 1

If this tree is stored in an array, it can be rearranged to be "level continuous" (the first element is the root, the next two its children, the next four their children, etc), and the problem is trivial.

If it is stored in another way, it becomes problematic. You could try a breadth-first traversal, but that can consume O(n) memory.

Well I guess you can create an O(n log n) time algorithm by storing the current level and the path to the current element (represented as a binary number), and only storing the last visited element to be able to create pairs. Only O(1 + log n) memory. -> This might actually be an O(n) algorithm with backtracking (see below).

I know there is an easy algorithm that visits all nodes in order in O(n), so there might be a trick to visit "sister" nodes in order in O(n) time. O(n log n) time is guaranteed tho, you could just stop at a given level.

There is a trivial O(n log n) algorithm as well, you just have to filter the nodes for a given level, increasing the level for the next loop.

Edit:

Okay, I created a solution that runs in O(n) with O(1) memory (two machine word sized variables to keep track of the current and maximal level /which is technically O(log log n) memory, but let's gloss over that/ and a few Nodes), but it requires that all Nodes contain a pointer to their parent. With this special structure it is possible to do an inorder traversal without an O(n log n) stack, only using two Nodes for stepping either left, up or right. You stop at a particular maximum level and never go below it. You keep track of the actual and the maximum level, and the last Node you encountered on the maximum level. Obviously you can print out such pairs if you encounter the next at the max level. You increase the maximum level each time you realize there is no more on that level.

Starting from the root Node in an n-1 node binary tree, this amounts to 1 + 3 + 7 + 15 + ... + n - 1 operations. This is 2 + 4 + 8 + 16 + ... + n - log2n = 2n - log2n = O(n) operations.

Without the special Node* parent members, this algorithm is only possible with O(log n) memory due to the stack needed for the in-order traversal.

Answer 2

Assuming you have the following structure as your tree:

struct Node
{
    Node *left;
    Node *right;
    int value;
};

You can print out all pairs in three passes modifying the tree in place. The idea is to link nodes at the same depth together with their right pointer. You traverse down by following left pointers. We also maintain a count of expected nodes for each depth since we don't null terminate the list for each depth. Then, we unzip to restore the tree to its original configuration.

The beauty of this is the zip_down function; it "zips" together two subtrees such that the right branch of the left subtree points to the left branch of the right subtree. If you do this for every subtree, you can iterate over each depth by following the right pointer.

struct Node
{
    Node *left;
    Node *right;
    int value;
};

void zip_down(Node *left, Node *right)
{
    if (left && right)
    {
        zip_down(left->right, right->left);
        left->right= right;
    }
}

void zip(Node *left, Node *right)
{
    if (left && right)
    {
        zip(left->left, left->right);
        zip_down(left, right);
        zip(right->left, right->right);
    }
}

void print_pairs(const Node * const node, int depth)
{
    int count= 1 << depth;

    for (const Node *node_iter= node; count > 1; node_iter= node_iter->right, --count)
    {
        printf("(%c, %c) ", node_iter->value, node_iter->right->value);
    }

    if (node->left)
    {
        print_pairs(node->left, depth + 1);
    }
}

void generate_tree(int depth, Node *node, char *next)
{
    if (depth>0)
    {
        (node->left= new Node)->value= (*next)++;
        (node->right= new Node)->value= (*next)++;

        generate_tree(depth - 1, node->left, next);
        generate_tree(depth - 1, node->right, next);
    }
    else
    {
        node->left= NULL;
        node->right= NULL;
    }
}

void print_tree(const Node * const node)
{
    if (node)
    {
        printf("%c", node->value);
        print_tree(node->left);
        print_tree(node->right);
    }
}

void unzip(Node * const node)
{
    if (node->left && node->right)
    {
        node->right= node->left->right;
        assert(node->right->value - node->left->value == 1);
        unzip(node->left);
        unzip(node->right);
    }
    else
    {
        assert(node->left==NULL);
        node->right= NULL;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char value_generator= 'a';
    Node root;

    root.value= value_generator++;
    generate_tree(2, &root, &value_generator);
    print_tree(&root);
    printf("\n");

    zip(root.left, root.right);
    print_pairs(&root, 0);
    printf("\n");

    unzip(&root);
    print_tree(&root);
    printf("\n");

    return 0;
}

EDIT4: in-place, O(n) time, O(log n) stack space.