Navigating basic binary tree

Question

So I need to create a basic binary tree for my application, but I'm having trouble conceptualising how to 'navigate', even in the process of generation.

Each node of course has an address, and leads to two other nodes which respectively hold a positive and negative value. My question is, if I want to create the tree using a loop, how do I do it? On the first iteration there will be two nodes, on the third there will be four and so on - how do I loop through each of their addresses before advancing my loop?

    for(int i=1;i<=5;i++){
        (*currentAddress).value = i;
        (*currentAddress).positive = i;
        (*currentAddress).negative = i*-1;
        //update current address
    }

Do I have to use BFS every iteration and just keep adding nodes until I've created (2^n-1) nodes?

Answer 1

So you want to create a full binary tree of a specified depth using a loop. That`s possible. But you should really consider @PaulColdrey`s answer first, as it is quite a bit simpler.

To create a binary tree iteratively, one has to know that its every node can be uniquely identified with a bit vector:

layer 0:                       ___________________[0]___________________ 
                              |                                         |
layer 1:            ________[00]________                       ________[10]________ 
                   |                    |                     |                    |
layer 2:      ___[000]___          ___[100]___           ___[010]___          ___[110]___ 
             |           |        |           |         |           |        |           |
layer 3:  [0000]       [1000]  [0100]       [1100]   [0010]       [1010]  [0110]       [1110]

A bit on Nth position tells which branch (left: 0 / right: 1) has been taken when going from (N – 1)th layer to Nth. In other words, a bit vector is a path to the node; see above.

It is sufficient to count from 0 to 2^K – 1 to get all possible paths to Kth layer nodes. And on top of that, when counting up, Nth bit would never change from 0 to 1 until all less significant bits change from 0 to 1 — which in this case means that the current Nth layer subtree is full.

This allows to only remember one current node per layer, recreating all children when a parent node changes.

This is how it looks in C:

struct NODE {
    struct NODE *side[2];
    double data;
};

struct NODE *fulltree(int depth) {
    struct NODE *curr[16] = {};
    int path, layer;

    if ((depth >= 0) && (depth < 16)) { /** reject exceedingly large trees **/
        curr[0] = (struct NODE*)calloc(1, sizeof(struct NODE));
        for (path = 0; path < (1 << depth); ++path)
            for (layer = 1; layer <= depth; ++layer)
                if (((path ^ (path - 1)) >> (depth - layer)) & 1) {
                    curr[layer - 1]->side[(path >> (depth - layer)) & 1] =
                    curr[layer] = (struct NODE*)calloc(1, sizeof(struct NODE));
                    curr[layer]->data =
                    ((path >> (layer - 1)) & 1)? layer : -layer;
                }
    }
    return curr[0];
}

The code assumes that negative integers on the target CPU are two`s complement.

Answer 2

You would actually want left and right pointers, right? And then you probably want to use recursion. For example (in some randomish language):

function Node* MakeNode(value, limit) {
    Node* node = new Node();
    (*node).value = value;
    // don't create any more children once we get to the depth limit.
    if (value < limit) {
        (*node).positive = MakeNode(value + 1);
        (*node).negative = MakeNode(value - 1);
    }
    return node;
}

// create a 5 deep tree
MakeNode(0, 5);