Binary Search Tree(BST)

• Binary Search Tree(BST) is the restrictive form of an general Binary Tree.
• Binary Search Tree contains the ‘SEARCH’ in their name, So it indicate that BST is an Tree Data Structure ,which provide easy searching Operations.
• Worst Case Time complexity of Binary tree is O(n).
• BST reduces the Searching complexity into O(logn) from O(n).

Binary Search Tree(BST) Definition

• Left subtree of Binary Search tree (BST) is always less than root node.
• Right subtree of Binary Search tree(BST) is always greater than the root node.
• All the Subtree must be in the form of Binary tree.

See the Example :

• in BST-1 , root node value 60 is greater than left node value 50. So follow the BST Property.
• in BST-2 , root node value 60 is greater than left node value 50 and less than the right node value 90.So follow the BST Property.

Binary Search Tree Node Representation

• Similar to the Binary Tree, we can declare an Binary Search Tree node in C and C++.

struct binarySearchTreeNode
{
   int DataElement;
   struct binarySearchTreeNode* left;
   struct binarySearchTreeNode* right;
}

Operations of Binary Search Tree(BST)

There are some basic operation ,which can apply on the BST :

• Insertion : Addition of a node.
• Deletion : Removal of a node.
• Searching : Finding the specific elements.
• Traversing : Visiting on all the node at least once.
• And many more :