creating binary tree not binary search tree

Question

I want to create a binary tree which fills from left to right. i.e. if 1,2,3 are to be inserted then the tree should look like

   1
 /   \
2     3

I wrote an insert function, to insert the nodes in the tree. For the first node everything works okay..But, for the next node's (if I want to insert 4,5 as children to 2 and later 6,7 as children to 3) how should I switch between the parents (2,3)?

Here's my insert function

struct node * Insert(struct node * node, int data) {
if(node == NULL)
    return (newNode(data));
else {
    if(!node->left)
        node->left = Insert(node->left,data);
    if(!node->right)
        node->right = Insert(node->right,data);
    //can't figure out the condition when they both fail
}
}

do you have a copy of the art of computer programming? or just a college cs book that has some graph theory? this is just very basic stuff — Grady Player
I'm struggling to see why you're not doing this with an array. Each child of some node at some arbitrary index n can be found at left: 2n+1 and right: 2(n+1). It would make your insertion trivial, since all you're doing is tacking nodes on to the end of a sequence, resizing it as needed. Btw, this is commonly how binary heaps are maintained for, among other reasons, the simplicity of their indexing algorithms. Unrelated: struct node * node an interesting, if not self-cryptic, choice of parameter names. — WhozCraig

BLUEPIXY BLUEPIXY · Accepted Answer · 2014-05-15T09:37:03

struct node **InsertPoint(struct node **node, int *level){
    if(*node == NULL)
        return node;

    int left_level, right_level;
    struct node **left_node, **right_node;
    left_level = right_level = *level + 1;
    left_node  = InsertPoint(&(*node)->left,  &left_level );
    right_node = InsertPoint(&(*node)->right, &right_level);
    if(left_level <= right_level){
        *level = left_level;
        return left_node;
    } else {
        *level = right_level;
        return right_node;
    }
}

struct node *Insert(struct node *node, int data) {
    struct node **np;
    int level = 0;
    np = InsertPoint(&node, &level);
    *np = newNode(data);
    return node;
}

creating binary tree not binary search tree

1 Answers