Binary Search Tree w3college.com

BINARY SEARCH TREE  

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

·        The value of the key of the left sub-tree is less than the value of its parent (root) node's key.

·        The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) nodes key.

·        All key's of a binary search tree must be distinct.

·        All key's in the left sub-tree 'T' are less than the root element (node).

·        All key's in the right sub-tree 'T' are greater than the root element (node).  

2.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 :

Binary Search Tree(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 :−

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

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 − Traverses a tree in an in-order manner.

·        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;

};

Search Operation :

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node for Pseudo code for Search Operation

struct node* search(int data){

   struct node *current = root;

   printf("Visiting elements: ");

          

   while(current->data != data){

          

      if(current != NULL) {

         printf("%d ",current->data);

                                

         //go to left tree

         if(current->data > data){

            current = current->leftChild;

         }  //else go to right tree

         else {               

            current = current->rightChild;

         }

                                

         //not found

         if(current == NULL){

            return NULL;

         }

      }                         

   }

  

   return current;

}

Insert Operation 

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

Algorithm for Insertion Operation

void insert(int data) {

   struct node *tempNode = (struct node*) malloc(sizeof(struct node));

   struct node *current;

   struct node *parent;

 

   tempNode->data = data;

   tempNode->leftChild = NULL;

   tempNode->rightChild = NULL;

 

   //if tree is empty

   if(root == NULL) {

      root = tempNode;

   } else {

      current = root;

      parent = NULL;

 

      while(1) {               

         parent = current;

                                

         //go to left of the tree

         if(data < parent->data) {

            current = current->leftChild;               

            //insert to the left

                                           

            if(current == NULL) {

               parent->leftChild = tempNode;

               return;

            }

         }  //go to right of the tree

         else {                                  

            current = current->rightChild;

           

            //insert to the right

            if(current == NULL) {

               parent->rightChild = tempNode;

               return;

            }

         }

      }           

   }

}       

 

Summary :

• BST is an advanced level algorithm that performs various operations based on the comparison of node values with the root node.
• Any of the points in a parent-child hierarchy represents the node. At least one parent or root node remains present all the time.
• There are a left subtree and right subtree. The left subtree contains values that are less than the root node. However, the right subtree contains a value that is greater than the root node.
• Each node can have either zero, one, or two children.
• A binary search tree facilitates primary operations like search, insert, and delete.
• Delete being the most complex have multiple cases, for instance, a node with no child, node with one child, and node with two children.
• The algorithm is utilized in real-world solutions like games, autocomplete data, and graphics.