Binary Search Tree

When we place constraints on how data elements can be stored in the tree, the items must be stored in such a way that the key values in left subtree of the root are less than the key value of the root, and the key values of all the nodes in the right subtree of the root are greater than the key value of the root. When this relationship holds in all the nodes in the tree then the tree is known as binary search tree.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties -

• The left sub-tree of a node has a key less than or equal to its parent node's key.

• The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as -

left_subtree (keys) = node (key) = right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST -

Basic Operations

Following are the basic operations of a tree -

• Search - Searches an element in a tree.

• Insert - Inserts an element in a tree.

• Pre-order Traversal - Traverses a tree in a pre-order manner.

• In-order Traversal – An inorder traversal of a binary search trees visits the keys in increasing order.

• Post-order Traversal - Traverses a tree in a post-order manner.

Node

Define a node having some data, references to its left and right child nodes.

struct node {
int data; 
struct node *leftChild;
struct node *rightChild;
};

Listing: The following program is showing the implementation and operations performed on binary search tree.

// C program to demonstrate insert operation in binary search tree
#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 \n", 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;
}

// 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:

20
30
40
50
60
70
80