Adding a node to a complete tree

Question

I'm trying to make complete tree from scratch in C++:

1st node = root
2nd node = root->left
3rd node = root->right
4th node = root->left->left
5th node = root->left->right
6th node = root->right->left
7th node = root->right->right

where the tree would look something like this:

                 NODE
              /        \
          NODE          NODE
       /        \    /        \
    NODE      NODE  NODE      NODE
    /
NEXT NODE HERE

How would I go about detecting where the next node would go so that I can just use one function to add new nodes? For instance, the 8th node would be placed at root->left->left->left

The goal is to fit 100 nodes into the tree with a simple for loop with insert(Node *newnode) in it rather than doing one at a time. It would turn into something ugly like:

100th node = root->right->left->left->right->left->left

Answer 1

Use a queue data structure to accomplish building a complete binary tree. STL provides std::queue.

Example code, where the function would be used in a loop as you request. I assume that the queue is already created (i.e. memory is allocated for it):

// Pass double pointer for root, to preserve changes
void insert(struct node **root, int data, std::queue<node*>& q)
{
    // New 'data' node
    struct node *tmp = createNode(data);

    // Empty tree, initialize it with 'tmp'
    if (!*root)
        *root = tmp;
    else
    {
        // Get the front node of the queue.
        struct node* front = q.front();

        // If the left child of this front node doesn’t exist, set the
        // left child as the new node.
        if (!front->left)
            front->left = tmp;

        // If the right child of this front node doesn’t exist, set the
        // right child as the new node.
        else if (!front->right)
            front->right = tmp;

        // If the front node has both the left child and right child, pop it.
        if (front && front->left && front->right)
            q.pop();
    }

    // Enqueue() the new node for later insertions
    q.push(tmp);
}

Answer 2

Suppose root is node#1, root's children are node#2 and node#3, and so on. Then the path to node#k can be found with the following algorithm:

1. Represent k as a binary value, k = { k_{n-1}, ..., k_0 }, where each k_i is 1 bit, i = {n-1} ... 0.
2. It takes n-1 steps to move from root to node#k, directed by the values of k_{n-2}, ..., k_0, where
   1. if k_i = 0 then go left
   2. if k_i = 1 then go right

For example, to insert node#11 (binary 1011) in a complete tree, you would insert it as root->left->right->right (as directed by 011 of the binary 1011).

Using the algorithm above, it should be straightforward to write a function that, given any k, insert node#k in a complete tree to the right location. The nodes don't even need to be inserted in-order as long as new nodes are detected created properly (i.e. as the correct left or right children, respectively).