Binary Tree Representation in C:

Binary Tree Representation in C:

A tree is represented by a pointer to the topmost node in tree. If the tree is empty, then value of root is NULL.
A Tree node contains following parts.
1. Data
2. Pointer to left child
3. Pointer to right child

In C, we can represent a tree node using structures. Below is an example of a tree node with an integer data.

First Simple Tree in C
Let us create a simple tree with 4 nodes in C. The created tree would be as following.

tree
----
1    <-- root
/   \
2     3
/
4
struct node
{
int data;
struct node *left;
struct node *right;
};

/* newNode() allocates a new node with the given data and NULL left and
right pointers. */
struct node* newNode(int data)
{
// Allocate memory for new node
struct node* node = (struct node*)malloc(sizeof(struct node));

// Assign data to this node
node->data = data;

// Initialize left and right children as NULL
node->left = NULL;
node->right = NULL;
return(node);
}

int main()
{
/*create root*/
struct node *root = newNode(1);
/* following is the tree after above statement

1
/   \
NULL  NULL
*/

root->left        = newNode(2);
root->right       = newNode(3);
/* 2 and 3 become left and right children of 1
1
/   \
2      3
/    \    /  \
NULL NULL NULL NULL
*/

root->left->left  = newNode(4);
/* 4 becomes left child of 2
1
/       \
2          3
/   \       /  \
4    NULL  NULL  NULL
/  \
NULL NULL
*/

getchar();
return 0;
}