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, Aug 03 '17 at 07: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, Aug 03 '17 at 07: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, Aug 03 '17 at 07: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, Aug 03 '17 at 08:43
Also note that you are not actually creating a **complete binary tree**. See https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees for what a complete binary tree is supposed to look like - it requires a lot of re-balancing on each insert. — grek40, Aug 03 '17 at 08:48
Possible duplicate of [Arrow operator (->) usage in C](https://stackoverflow.com/questions/2575048/arrow-operator-usage-in-c) — underscore_d, Aug 03 '17 at 09:58

grek40 · Accepted Answer · 2017-08-03T10:00:08.817

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.

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 ) — vivkv, Aug 04 '17 at 08:33
@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. — grek40, Aug 04 '17 at 08:38

Adding to a complete binary tree using recursion in C

1 Answers1