C Program to Implement Binary Tree
The below program demonstrates all the basic operations on a binary search tree: creation, searching, traversal, insertion and deletion in C.
// C program to to implement binary tree
#include <stdio.h>
#include <stdlib.h>
// Define a structure for tree nodes
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Function to create a new node
Node* createNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function for inserting a node in a binary tree
void insert(Node** root, int data)
{
Node* newNode = createNode(data);
if (*root == NULL) {
*root = newNode;
return;
}
// Level order traversal to find the appropriate place
// for insertion
Node* temp;
Node* queue[100];
int front = -1, rear = -1;
queue[++rear] = *root;
while (front != rear) {
temp = queue[++front];
// Insert new node as the left child
if (temp->left == NULL) {
temp->left = newNode;
return;
}
// if left child is not missing push it to the queue
else {
queue[++rear] = temp->left;
}
// Insert new node as the right child
if (temp->right == NULL) {
temp->right = newNode;
return;
}
// if right child is not missing push it to the
// queue
else {
queue[++rear] = temp->right;
}
}
}
// Function to perform level order traversal to find the
// deepest rightmost node
Node* getDeepestRightmostNode(Node* root)
{
Node* temp;
Node* queue[100];
int front = -1, rear = -1;
queue[++rear] = root;
while (front != rear) {
temp = queue[++front];
if (temp->left != NULL) {
queue[++rear] = temp->left;
}
if (temp->right != NULL) {
queue[++rear] = temp->right;
}
}
return temp;
}
// Function for deleting deepest rightmost node in a binary
// tree
void deleteDeepestRightmostNode(Node* root, Node* dNode)
{
Node* temp;
Node* queue[100];
int front = -1, rear = -1;
queue[++rear] = root;
while (front != rear) {
temp = queue[++front];
if (temp == dNode) {
temp = NULL;
free(dNode);
return;
}
if (temp->right != NULL) {
if (temp->right == dNode) {
temp->right = NULL;
free(dNode);
return;
}
else {
queue[++rear] = temp->right;
}
}
if (temp->left != NULL) {
if (temp->left == dNode) {
temp->left = NULL;
free(dNode);
return;
}
else {
queue[++rear] = temp->left;
}
}
}
}
// Function to delete a node in the binary tree
void delete (Node** root, int data)
{
if (*root == NULL) {
printf("Tree is empty.\n");
return;
}
if ((*root)->left == NULL && (*root)->right == NULL) {
if ((*root)->data == data) {
free(*root);
*root = NULL;
return;
}
else {
printf("Node not found.\n");
return;
}
}
Node* temp;
Node* queue[100];
int front = -1, rear = -1;
queue[++rear] = *root;
Node* keyNode = NULL;
while (front != rear) {
temp = queue[++front];
if (temp->data == data) {
keyNode = temp;
}
if (temp->left != NULL) {
queue[++rear] = temp->left;
}
if (temp->right != NULL) {
queue[++rear] = temp->right;
}
}
if (keyNode != NULL) {
Node* deepestNode = getDeepestRightmostNode(*root);
keyNode->data = deepestNode->data;
deleteDeepestRightmostNode(*root, deepestNode);
}
else {
printf("Node not found.\n");
}
}
// Function to search for a node in the binary tree
Node* search(Node* root, int data)
{
if (root == NULL) {
return NULL;
}
Node* temp;
Node* queue[100];
int front = -1, rear = -1;
queue[++rear] = root;
while (front != rear) {
temp = queue[++front];
if (temp->data == data) {
return temp;
}
if (temp->left != NULL) {
queue[++rear] = temp->left;
}
if (temp->right != NULL) {
queue[++rear] = temp->right;
}
}
return NULL;
}
// function to perform inorder traversal in a binary tree
void inorderTraversal(Node* root)
{
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
int main()
{
Node* root = NULL;
// Inserting nodes
insert(&root, 20);
insert(&root, 30);
insert(&root, 40);
insert(&root, 50);
insert(&root, 60);
insert(&root, 70);
insert(&root, 80);
// Inorder traversal
printf("Inorder traversal of the given Binary Search "
"Tree is: ");
inorderTraversal(root);
printf("\n");
// Deleting a node
int deleteValue = 20;
delete (&root, deleteValue);
printf("After deletion of %d: ", deleteValue);
inorderTraversal(root);
printf("\n");
// Inserting a new node
int insertValue = 25;
insert(&root, insertValue);
printf("After insertion of %d: ", insertValue);
inorderTraversal(root);
printf("\n");
// Searching for a node
int target = 25;
Node* searchResult = search(root, target);
if (searchResult != NULL) {
printf("Node %d found in the BST.\n", target);
}
else {
printf("Node %d not found in the BST.\n", target);
}
return 0;
}
Output
Inorder traversal of the given Binary Search Tree is: 50 30 60 20 70 40 80 After deletion of 20: 50 30 60 80 70 40 After insertion of 25: 50 30 60 80 70 40 25 Node 25 found in the BST.
Time Complexity: O(N), here N is the number of nodes in a binary tree.
Auxilliary Space: O(N)
Binary Tree in C
A binary tree is a non-linear hierarchical data structure in which each node has at most two children known as the left child and the right child. It can be visualized as a hierarchical structure where the topmost node is called the root node and the nodes at the bottom are called leaf nodes or leaves.
In this article, we will learn the basics of binary trees, types of binary trees, basic operations that can be performed on binary trees as well as applications, advantages, and disadvantages of binary trees in C.
Contact Us