Binary Tree Structure in C

Binary trees are a type of Tree data structure wherein each node has at-most 2 child nodes. We've already discussed about Tree data structure. So, in this article we're gonna talk about the implementation of Binary Trees in C. This is how a Binary Tree looks like. As you can see here, no node has more than 2 child nodes.

Basic structure of Binary Tree

Based on what we've discussed so far, a node of a Binary Tree contains:

A value
Left child node
Right child node

So, based on the above list, we'll make a structure for the same in c. It looks something like this -

typedef struct node{
    int data;
    struct node *left;
    struct node *right;
    
}NODE;

Here, "left" is a pointer to the Left Child Node and the "right" is a pointer to the Right Child Node.

You can understand this structure by relating it to Linked Lists as well. In linked list we had a pointer called "next", which pointed to the next node of the list, similarly, we have "left" and "right" pointers to point at the left and right child nodes.

Creating a New Node

Now, we're gonna create a new node which will contain the integer value that's gonna be entered by the user. It looks like this -

NODE *createnode(int val){
    NODE *newnode = (NODE *)malloc(sizeof(NODE))
    newnode->data = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

So, as you can see: -> First we allocate a new block of memory of "NODE" size to the newnode. -> Then we set the data value of the newnode to the value entered by the user(passed through the argument of the function). -> Then we set both, "right" and "left" equal to "NULL" initially. Later in the program we'll assign values to them.