Binary Tree in C Using Recursion

Here you will get program to create binary tree in C using recursion.

What is Binary Tree?

A tree is said to be a binary tree if each node of the tree can have maximum of two children. Children of a node of binary tree are ordered. One child is called left child and the other is called right child. An example of binary tree is shown in below diagram.

Also Read: Binary Search Tree in C

Creation of Binary Tree Using Recursion

A binary tree can be created recursively. The program will work as follow:

1. Read a data in x.
2. Allocate memory for a new node and store the address in pointer p.
3. Store the data x in the node p.
4. Recursively create the left subtree of p and make it the left child of p.
5. Recursively create the right subtree of p and make it the right child of p.

Program to Create Binary Tree in C Using Recursion

#include<stdio.h>

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

node *create()
{
	node *p;
	int x;
	printf("Enter data(-1 for no data):");
	scanf("%d",&x);
	
	if(x==-1)
		return NULL;
	
	p=(node*)malloc(sizeof(node));
	p->data=x;
	
	printf("Enter left child of %d:\n",x);
	p->left=create();

	printf("Enter right child of %d:\n",x);
	p->right=create();
	
	return p;
}

void preorder(node *t)		//address of root node is passed in t
{
	if(t!=NULL)
	{
		printf("\n%d",t->data);		//visit the root
		preorder(t->left);		//preorder traversal on left subtree
		preorder(t->right);		//preorder traversal om right subtree
	}
}

int main()
{	
	node *root;
	root=create();
	printf("\nThe preorder traversal of tree is:\n");
	preorder(root);
	
	return 0;
}

Output

Enter data(-1 for no data):5
Enter left child of 5:
Enter data(-1 for no data):7
Enter left child of 7:
Enter data(-1 for no data):8
Enter left child of 8:
Enter data(-1 for no data):3
Enter left child of 3:
Enter data(-1 for no data):-1
Enter right child of 3:
Enter data(-1 for no data):-1
Enter right child of 8:
Enter data(-1 for no data):-1
Enter right child of 7:
Enter data(-1 for no data):-1
Enter right child of 5:
Enter data(-1 for no data):-1

The preorder traversal of tree is:

5
7
8
3