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).

Answer 3

Assuming tree is always complete we may use next recursion. It does not gives best perfomance, but it is easy to understand

Node* root;
Node*& getPtr(int index){
    if(index==0){
       return root;    
    }
    if(index%2==1){
       return (getPtr( (index-1)/2))->left;
    }
    else{
       return (getPtr( (index-2)/2))->right;
    }
}

and then you use it like

for(int i = 0; i<100; ++i){
  getPtr(i) = new Node( generatevalue(i) );
}

Answer 4

 private Node addRecursive(*Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    if (value < current.value) {
        current->left = addRecursive(current->left, value);
    } else if (value > current->value) {
        current->right = addRecursive(current->right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
 }

I do not know that if your Nodes has got a value instance but: With this code you can have a sorted binary tree by starting from the root. if the new node’s value is lower than the current node’s, we go to the left child. If the new node’s value is greater than the current node’s, we go to the right child. When the current node is null, we’ve reached a leaf node and we can insert the new node in that position.