Computer Science‎ > ‎

## Binary Search Trees

```To go through the C program / source-code, scroll down this pageBinary 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#includetypedef 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
 Tree Data Structures Binary Search Trees Heaps Height Balanced Trees Graphs and Graph Algorithms Depth First Search Breadth First Search Minimum Spanning Trees: Kruskal Algorithm Minumum Spanning Trees: Prim's Algorithm Dijkstra Algorithm for Shortest Paths Floyd Warshall Algorithm for Shortest Paths Bellman Ford Algorithm Popular Algorithms in Dynamic Programming Dynamic Programming Integer Knapsack problem Matrix Chain Multiplication Longest Common Subsequence Greedy Algorithms Elementary cases : Fractional Knapsack Problem, Task Scheduling Data Compression using Huffman Trees