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.

3 comments :

  1. Very good information indeed. Thanks for posting this here. You can find more information on Binary search tree (BST) here in the following link with examples.

    Binary search tree (BST) in Cpp with examples

    ReplyDelete

Spam comments will be deleted. :)

 
Loading...
TOP