This is a C Program to perform insertion opertion in binary search tree. A new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
Here is source code of the C Program to Perform Insertion in a BST. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<stdio.h>
#include<stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item) {
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do inorder traversal of BST
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key) {
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// Driver Program to test above functions
int main() {
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// print inoder traversal of the BST
inorder(root);
return 0;
}
Output:
$ gcc InsertionBST.c $ ./a.out 20 30 40 50 60 70 80
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Related Posts:
- Check Computer Science Books
- Practice Programming MCQs
- Check Programming Books
- Apply for Computer Science Internship
- Practice Design & Analysis of Algorithms MCQ