A tree in which all of the nodes can have two children or siblings (at most) is called a binary tree. A binary tree has the following characteristics:

• A tree contains, at most, 2l nodes at level l.
• If a binary tree contains m nodes at level l, it contains at most 2m nodes at level l+1.
• A tree contains 2d leaves and therefore 2d-1 non-leaf nodes, where d is its depth.
• A binary tree with n internal nodes has (n+1) external nodes.
• A binary tree with n nodes has exactly n+1 NULL links

Binary Search Tree Program in C

Let's create a file named binarysearchtree.c and add the following source code to it:

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

#define max 10

struct tree
{
	int data;
	struct tree *right;
	struct tree *left;
};

void build(int Arr[], int Len);
struct tree *makeroot(int val);
void rightchild(struct tree * rootNode, int val);
void leftchild(struct tree *rootNode, int val);
void travino(struct tree *node);

int main()
{
	int arr[max],i,len;
	printf("How many elements are there for making the binary search tree? ");
	scanf("%d", &len);
	printf("Enter %d elements in array \n",len);
	for(i=0;i<len;i++)
		scanf("%d",&arr[i]);
	build(arr,len);
	return 0;
}

void build(int Arr[], int Len)
{
	struct tree *temp, *rootNode;
	int j;
	rootNode=makeroot(Arr[0]);
	for(j=1;j<Len;j++)
	{
		temp=rootNode;	
		while (1)
		{
			if(Arr[j] < temp->data )
			{
				if(temp->left !=NULL)
				{
					temp=temp->left;
					continue;
				}
				leftchild(temp,Arr[j]);
			}
			if(Arr[j] >temp->data)
			{
				if(temp->right !=NULL)
				{
					temp=temp->right;
					continue;
				}
				rightchild(temp,Arr[j]);
			}
			break;
		}
	}
	printf ("Binary Search Tree is created\n");
	printf("The inorder traversal of the tree is as follows:\n");
	travino(rootNode);
}

struct tree *makeroot(int val)
{
	struct tree *rootNode;
	rootNode=(struct tree *)malloc(sizeof(struct tree));
	rootNode->data=val;
	rootNode->right=NULL;
	rootNode->left=NULL;
	return rootNode;
}

void leftchild(struct tree *rootNode, int val)
{
	struct tree *newNode;
	newNode=(struct tree *)malloc(sizeof(struct tree));
	newNode->data=val;
	newNode->left=NULL;
	newNode->right=NULL;
	rootNode->left=newNode;
}

void rightchild(struct tree *rootNode, int val)
{
	struct tree *newNode;
	newNode=(struct tree *)malloc(sizeof(struct tree));
	newNode->data=val;
	newNode->left=NULL;
	newNode->right=NULL;
	rootNode->right=newNode;
}

void travino(struct tree *node)
{
	if (node!=NULL)
	{
		travino(node->left);
		printf ("%d\t",node->data);
		travino(node->right);
	}
}

To compile and run the above C program, you can use C Programs Compiler Online tool.

Output:

How many elements are there for making the binary search tree? 10
Enter 10 elements in array 
9
7
8
5
6
3
4
1
2
3
Binary Search Tree is created
The inorder traversal of the tree is as follows:
1	2	3	4	5	6	7	8	9