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

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.

BST [ fig. Wikimedia ] |

- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- Each node can have up to two successor nodes.
- There must be no duplicate nodes.
- 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.