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?

Have a look at pre-order, post-order and in-order tree traversal. That should point you in the right direction. — jigglypuff, Oct 18 '16 at 22:46
Possible duplicate of [Binary Tree Insert Algorithm](http://stackoverflow.com/questions/16630823/binary-tree-insert-algorithm) — Hans Z, Oct 18 '16 at 22:46
Note: array indexes are from 0 to n-1. So: `for(int i=0;i<5;i++) ...` — Paul Ogilvie, Oct 18 '16 at 22:48
Please learn, what is a binary tree (its structure). There is no positive or negative value in two other nodes. There are smaller values in the left subtree and greater values in the right subtree. Only after a proper understanding, you can start thinking about algorithms. — Ivan Kuckir, Oct 18 '16 at 22:56
Thank you everyone! And yes Ivan my tree differs in this regard, I already know what all the nodes are going to contain beforehand (the same number in each 'level of depth', only one is positive and the other negative. — Coma, Oct 18 '16 at 23:06
Please edit your question with the declaration for `currentAddress` and its struct. — Code-Apprentice, Oct 19 '16 at 02:25

score 1 · Answer 1 · answered Oct 18 '16 at 22:51

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

Thank you! I will try to apply and fully understand this and get back to you. — Coma, Oct 18 '16 at 23:09

hidefromkgb · Answer 2 · 2016-10-19T02:42:37.110

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.

Navigating basic binary tree

2 Answers2