C Program to Perform Insertion in Binary Search Tree

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.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Double Order Traversal of a Binary Tree

» Next - C Program to Print All Nodes of a Tree

Related Posts:

Check Programming Books
Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books
Apply for Computer Science Internship

Recommended Articles: