Inserting in a Complete Binary Tree

Question

I'm trying to insert into a complete binary tree for a school assignment. The structure of my tree is as such

typedef struct TreeNode {
void * data;
struct TreeNode * left;
struct TreeNode * right;
struct TreeNode * parent;
} TNode;

typedef struct CompleteBinaryTree {
TNode * root;
TNode * last;
int numelm;
} CBTree;

I have 4 ways of inserting depending the situation

The tree is empty
The tree as one node
The last node of the CBT is his parent left child
Finally I go up the tree as long as the current node is the right node of his parent, if the current node is not the root I will go to his brother and go down left, else I just go down left

I'm currently stuck on my third way and I don't know what is wrong with my code.

Could somebody push me in the right direction.

Thank you !

void CBTreeInsert(CBTree* tree, void* data) {
    TNode * tmp = newTNode(data);
    TNode * curr = tree->last;

    if(tree->root == NULL) //empty
    { 
        tree->root = tmp;
    }
    else if(tree->last == tree->root) //one node
    {
        tree->last->left = tmp;
    }
    else if(tree->last->parent->right == NULL) //general
    {
        tree->last->parent->right = tmp;
    }
    else if(tree->last->parent == tree->last->parent->right) //degenarated
    {
        while(curr->parent == curr->parent->right)
                curr = curr->parent;

        if(curr != tree->root)
        {
            curr = curr->parent->right;
            while(curr->left != NULL)
                curr = curr->left;
        }
        curr->left = tmp;
        }
    else
        {
            while(curr->left != NULL)
                curr = curr->left;

            curr->left = tmp;
        }
}
else
{
    fprintf(stderr,"Error\n");
}

tree->last = tmp;
tree->numelm++;
}

@Logica while I agree that adding a tree tag maks sense here, why do you feel that tags for "while" and "if" are relevant for this question? Edits which add irrelevant tags should not be accepted and the fact that something is used in shown code is NOT good enough a reason to use the tags. If you elaborate how the two tags are really relevant beyound "being used" your edit might be accepted soon. — Yunnosch
Crunchy, you are quite close to a consistent indentation scheme. Please also indent the first level however. Also, but this is purely opinion-based, my favorite scheme is to put all {} on a separate line and have pairs align on the same column. I.e. newline before each, indent after a { and outdent before a }. That scheme is widely used on StackOverflow. But it remains an opinion. Using any consistent scheme is fine. — Yunnosch
@Yunnosh I have made changes in my indentation scheme. Tell me if you think it's better now. — Crunchy
Your indentation is off. You can tell by the one else in the first column. If you did your indentation consistently that should not be possible. I am currently trying to find the source of this.... It is entirely possible that this inconsistency in indentation indicates an inconsistency in logic or at least syntax. I recommend to join me in trying to find the root of this, because it might lead to solving the actual problem you are asking about.... — Yunnosch
You have eight ccurrences of { but nine occurrences of }. You need to double check your symmetry. I did not try, but this should mean that the function cannot be compiled as is. Make sure that you provide a minimal reproducible example please. — Yunnosch

Chris Hall Chris Hall · Accepted Answer · 2020-02-10T18:49:33

I think you more or less had it, but:

I don't see where the new node's tmp->parent is set ?
the else if(tree->last->parent == tree->last->parent->right) is broken, I think this should be else if(tree->last == tree->last->parent->right), which should definitely be true at that point.
The while(curr->parent == curr->parent->right) curr = curr->parent; could be problematic for curr == tree->root, though that can be worked around by setting tree->root->parent = tree->root
you've got two copies of:

    while(curr->left != NULL)
    {
        curr = curr->left;
    }
    curr->left = tmp;`

I would be tempted to do:

else if (tree->last == tree->last->parent->right)
{
    TNode * curr = tree->last->parent ; // NB: know that tree->last != tree->root
                                        //     so can step up.  
    while (1)
    {
        if (curr == tree->root)
            break ;

        if (curr == curr->parent->left)
        {
            // The parent of the curr node is to the right of the last node, so
            // step to its right, and then insert to the extreme left of that.
            curr = curr->parent->right ;
            assert(curr != NULL) ;
            break ;
        } ;
        curr = curr->parent ;
    } ;

    // Arrive here with curr as root of sub-tree in which now want to insert the
    // new node as the left-most child.

    while (curr->left != NULL)
    {
        assert(curr->right != NULL) ;
        curr = curr->left ;
    } ;
    assert(curr->right == NULL) ;
    tmp->parent = curr ;
    curr->left  = tree->last = tmp;
}

but I haven't tested this. (And there are the other places where need to set tmp->parent.)

Inserting in a Complete Binary Tree

1 Answers