Computer Science‎ > ‎

Binary Search Trees - Tutorial with C Program Source Code and Documentation



Binary Search Trees


Binary Search Tree
 
To go through the C program / source-code, scroll down this page
Binary Search Tree:

A tree is a connected, acyclic, unidirectional graph. It emulates a tree structure with a set of linked nodes. The topmost node in a tree is called the root node, node of a tree that has child nodes is called an internal node or inner node and the bottom most nodes are called a leaf node. The root is a node that has no parent; it can have only child nodes. Leaves, on the other hand, have no children. The simplest form of a tree is a Binary Tree which has a root node and two subtrees (which is a portion of a    tree data structure that can be viewed as a complete tree in itself) - left and right. A Binary Search Tree is a binary tree in which if a node has value N, all values in its left sub-tree are less than N, and all values in its right sub-tree are greater than N. This property called binary search tree property holds for each and every node in the tree.
Basic operations of Binary Search tree are:

Finding a node with a specific data value.
Finding a node with minimum or maximum data value.
Insertion and deletion of a node.
Three (preorder, postorder and inorder) operations for depth-first traversal of a tree

a. Preorder: 

Visit a node before traversing it’s sub-trees

b. Inorder: 

Visit a node after traversing it’s left subtree but before traversing it’s right sub-tree

c. Postorder: 

Visit a node after traversing all of it’s subtrees

Binary search tree has three properties: data stands for the value of the node, *left is the left subtree of a node and *right (a pointer of type struct treeNode) is the right subtree of a node.

Complete Tutorial with Examples :


Source Code :


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

typedef struct treeNode
{
        int data;
        struct treeNode *left;
        struct treeNode *right;

}treeNode;

treeNode* FindMin(treeNode *node)
{
        if(node==NULL)
        {
                /* There is no element in the tree */
                return NULL;
        }
        if(node->left) /* Go to the left sub tree to find the min element */
                return FindMin(node->left);
        else 
                return node;
}
treeNode* FindMax(treeNode *node)
{
        if(node==NULL)
        {
                /* There is no element in the tree */
                return NULL;
        }
        if(node->right) /* Go to the left sub tree to find the min element */
                FindMax(node->right);
        else 
                return node;
}

treeNode * Insert(treeNode *node,int data)
{
        if(node==NULL)
        {
                treeNode *temp;
                temp = (treeNode *)malloc(sizeof(treeNode));
                temp -> data = data;
                temp -> left = temp -> right = NULL;
                return temp;
        }

        if(data >(node->data))
        {
                node->right = Insert(node->right,data);
        }
        else if(data < (node->data))
        {
                node->left = Insert(node->left,data);
        }
        /* Else there is nothing to do as the data is already in the tree. */
        return node;

Some Important Data Structures and Algorithms, at a glance:

Arrays : Popular Sorting and Searching Algorithms

 

  

Bubble Sort  

Insertion Sort 

Selection Sort Shell Sort

Merge Sort  

Quick Sort 

 
Heap Sort		 
Binary Search Algorithm

Basic Data Structures  and Operations on them


  

Stacks 

Queues  

 
 Single Linked List 
Double Linked List

Circular Linked List