Scribd
Upload
9 views

C program to implement binary search tree

This C program implements a binary search tree (BST) with functionalities to create nodes, insert, search, delete, and perform various tree traversals (post-order, in-order, pre-order). It includes functions for finding the minimum value in the tree and managing memory allocation for nodes. The main function demonstrates inserting nodes, searching for a specific key, and displaying the tree structure through different traversal methods.

Uploaded by

babinbista1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

C program to implement binary search tree

This C program implements a binary search tree (BST) with functionalities to create nodes, insert, search, delete, and perform various tree traversals (post-order, in-order, pre-order). It includes functions for finding the minimum value in the tree and managing memory allocation for nodes. The main function demonstrates inserting nodes, searching for a specific key, and displaying the tree structure through different traversal methods.

Uploaded by

babinbista1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

// C program to implement binary search tree

#include <stdio.h>

#include <stdlib.h>

// Define a structure for a binary tree node

struct BinaryTreeNode {

int key;

struct BinaryTreeNode *left, *right;

};

// Function to create a new node with a given value

struct BinaryTreeNode* newNodeCreate(int value)

struct BinaryTreeNode* temp

= (struct BinaryTreeNode*)malloc(

sizeof(struct BinaryTreeNode));

temp->key = value;

temp->left = temp->right = NULL;

return temp;

// Function to search for a node with a specific key in the

// tree

struct BinaryTreeNode*

searchNode(struct BinaryTreeNode* root, int target)

if (root == NULL || root->key == target) {

return root;

}
if (root->key < target) {

return searchNode(root->right, target);

return searchNode(root->left, target);

// Function to insert a node with a specific value in the

// tree

struct BinaryTreeNode*

insertNode(struct BinaryTreeNode* node, int value)

if (node == NULL) {

return newNodeCreate(value);

if (value < node->key) {

node->left = insertNode(node->left, value);

else if (value > node->key) {

node->right = insertNode(node->right, value);

return node;

// Function to perform post-order traversal

void postOrder(struct BinaryTreeNode* root)

if (root != NULL) {

postOrder(root->left);

postOrder(root->right);
printf(" %d ", root->key);

// Function to perform in-order traversal

void inOrder(struct BinaryTreeNode* root)

if (root != NULL) {

inOrder(root->left);

printf(" %d ", root->key);

inOrder(root->right);

// Function to perform pre-order traversal

void preOrder(struct BinaryTreeNode* root)

if (root != NULL) {

printf(" %d ", root->key);

preOrder(root->left);

preOrder(root->right);

// Function to find the minimum value

struct BinaryTreeNode* findMin(struct BinaryTreeNode* root)

if (root == NULL) {

return NULL;
}

else if (root->left != NULL) {

return findMin(root->left);

return root;

// Function to delete a node from the tree

struct BinaryTreeNode* delete (struct BinaryTreeNode* root,

int x)

if (root == NULL)

return NULL;

if (x > root->key) {

root->right = delete (root->right, x);

else if (x < root->key) {

root->left = delete (root->left, x);

else {

if (root->left == NULL && root->right == NULL) {

free(root);

return NULL;

else if (root->left == NULL

|| root->right == NULL) {

struct BinaryTreeNode* temp;

if (root->left == NULL) {
temp = root->right;

else {

temp = root->left;

free(root);

return temp;

else {

struct BinaryTreeNode* temp

= findMin(root->right);

root->key = temp->key;

root->right = delete (root->right, temp->key);

return root;

int main()

// Initialize the root node

struct BinaryTreeNode* root = NULL;

// Insert nodes into the binary search tree

root = insertNode(root, 50);

insertNode(root, 30);

insertNode(root, 20);

insertNode(root, 40);

insertNode(root, 70);
insertNode(root, 60);

insertNode(root, 80);

// Search for a node with key 60

if (searchNode(root, 60) != NULL) {

printf("60 found");

else {

printf("60 not found");

printf("\n");

// Perform post-order traversal

postOrder(root);

printf("\n");

// Perform pre-order traversal

preOrder(root);

printf("\n");

// Perform in-order traversal

inOrder(root);

printf("\n");

// Perform delete the node (70)

struct BinaryTreeNode* temp = delete (root, 70);

printf("After Delete: \n");

inOrder(root);
// Free allocated memory (not done in this code, but

// good practice in real applications)

return 0;

You might also like