C program to implement Binary Search Tree (BST)

A Binary Search Tree ( BST ) is a binary tree that maintains the following property:

BST [ fig. Wikimedia ]

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. The left and right subtree each must also be a binary search tree.
4. Each node can have up to two successor nodes.
5. There must be no duplicate nodes.
6. A unique path exists from the root to every other node.

C/C++ Implementation of BST:

The following program shows how to create and insert nodes to a Binary Search Tree.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int value;
    node* left;
    node* right;
};


struct node* root;

struct node* insert(struct node* r, int data);

int main()
{
    root = NULL;
    int n, v;

    printf("How many data's do you want to insert ?\n");
    scanf("%d", &n);

    for(int i=0; i<n; i++){
        printf("Data %d: ", i+1);
        scanf("%d", &v);
        root = insert(root, v);
    }
    return 0;
}

struct node* insert(struct node* r, int data)
{
    if(r==NULL) // BST is not created created
    {
        r = (struct node*) malloc(sizeof(struct node)); // create a new node
        r->value = data;  // insert data to new node
        // make left and right childs empty
        r->left = NULL;   
        r->right = NULL;
    }
    // if the data is less than node value then we must put this in left sub-tree
    else if(data < r->value){ 
        r->left = insert(r->left, data);
    }
    // else this will be in the right subtree
    else {
        r->right = insert(r->right, data);
    }
    return r;

}

Above program only inserts data / nodes to the binary tree. To print the tree, we need to know how to traverse a Binary Search Tree. Please visit this link to know how to traverse / print a BST.