Adding to a complete binary tree using recursion in C

Question

I am trying to learn recursion, so I tried one program to create a complete binary tree and then print the sum of all its elements, I wrote the insertion part myself and I am confused that my pointer variable "curr" which points to a tree node, why I am able to do "curr = curr->left" as it is just a pointer to a node. shouldn't only the actual tree node contain these left and right fields ? Just give me a heads up on this novice doubt. I am surprised that my program does the job though.

Thanks :)

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;
    struct node *left,*right;
};

struct node *head = NULL;
struct node *curr = NULL;

void insert_Data(int val,struct node* curr){
    struct node *tempnode = (struct node*)malloc(sizeof(struct node));
    tempnode->data = val;
    tempnode->left = NULL;
    tempnode->right = NULL;
    if(head==NULL){
        head = tempnode;
        curr = head;
        printf("head element is : %d\n",head->data);
    }
    else{
        if(curr->left == NULL){
            curr->left = tempnode;
        }
        else if(curr->right == NULL){
            curr->right = tempnode;
        }
        else{
            curr = curr->left;
            insert_Data(val,curr);
        }
    }
}

//to test program
int sumNode(struct node* root ) {
  // if there is no tree, its sum is zero
  if( root == NULL ) {
    return 0 ;

  } else { // there is a tree
   printf("element is = %d\n",root->data);
    return root->data + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int i;
    for(i=0;i<9;i++){
        insert_Data(arr[i],head);
    }
    int result = sumNode(head);
    printf("\n\n%d",result);
    return 0;
}

Well curr is a pointer to an instance of the node structure. The node structure has the members left and right. I'm not exactly sure where your confusion is coming from? — Some programmer dude
– Some programmer dude, Commented Aug 3, 2017 at 7:18
Thanks for quick reply @some programmer dude , actually my confusion is whether the node pointer that we create to point to an actual node , also contains these fields as the actual node does ? — vivkv
– vivkv, Commented Aug 3, 2017 at 7:20
Maybe this helps: curr->left is the same as (*curr).left. The pointer does not contain any fields. It just points to the struct that does. — Vítek
– Vítek, Commented Aug 3, 2017 at 7:47
As a side note: you create a heavy memory leak there... for a tree with depth 3, you malloc 3 times tempnode but you only use the last one. — grek40
– grek40, Commented Aug 3, 2017 at 8:43

grek40 · Accepted Answer · 2017-08-03 10:00:08Z

1

For the meaning of the arrow operator -> see this related question Arrow operator (->) usage in C.

Regarding the question title I suggest a recursive insert method, that follows a root in, root out pattern:

// in: the value to be inserted as new node
//     the head of the sub-tree that should contain the new node
// out: the new head of the subtree
struct node* insert_Data(int val, struct node* subtreeRoot);

As long as you don't rebalance the tree, this would basically result in a behavior where any valid subtreeRoot input would return itself with the new value added somewhere down the tree hierarchy and a NULL input would return the newly created node as output.

struct node* insert_Data(int val, struct node* subtreeRoot)
{
    if (subtreeRoot == NULL)
    {
        struct node *tempnode = (struct node*)malloc(sizeof(struct node));
        tempnode->data = val;
        tempnode->left = NULL;
        tempnode->right = NULL;
        return tempnode;
    }
    else if (val < subtreeRoot->data)
    {
        subtreeRoot->left = insert_Data(val, subtreeRoot->left);
    }
    else // val is bigger than the subtree root data
    {
        subtreeRoot->right = insert_Data(val, subtreeRoot->right);
    }
    return subtreeRoot;
}

Use like:

head = insert_Data(arr[i], head);

For now, the return value only helps in keeping the NULL comparisons in a single place. But as said, this signature and usage also allows a lot more sophisticated insert methods, where the subtree structure is completely changed on inserts.

edited Aug 3, 2017 at 10:00

answered Aug 3, 2017 at 9:54

grek40

13.5k1 gold badge29 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

vivkv Over a year ago

Thanks for pointing out my mistake of memory leak @grek40, one more doubt, should the complete binary tree be sorted as in the left child should be of low value than that of right child or it can be just any value located at any child ? Furthermore, to add up the values I must need a pointer to the root node right ? (so that I can traverse it )

grek40 Over a year ago

@CodeSpy Actually, the sorting is only relevant for binary search trees. I just used it because I didn't think of any better criteria - your idea of always going left when the current node already contains a right child will create very unbalanced trees. You can decide between left and right any way you want - but it's good to chose a strategy where the resulting tree will be somewhat balanced. Also, as commented, if you really need a complete binary tree, you have to change your approach.

Collectives™ on Stack Overflow

Adding to a complete binary tree using recursion in C

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related