binary search tree

Binary Search Tree (BST) is one such data structures that supports faster searching, rapid sorting, and easy insertion and deletion

BST is also known as sorted versions of binary tree.

BST is a node-based binary tree data structure which has the following properties:

·       The left subtree of a node contains only nodes with keys lesser than the node’s key.

·       The right subtree of a node contains only nodes with keys greater than the node’s key.

·       The left and right subtree each must also be a binary search tree.

BST also have multiple basic operations such as find, insert, and remove. Which all of them have their own unique commands.

-       Search

Because of the property of BST, finding/searching in BST is easy.

Let the key that we want to search is X.

o   We begin at root

o   If the root contains X then search terminates successfully.

o   If X is less than root’s key then search recursively on left sub tree, otherwise search recursively on right sub tree.

-       Insertion

Inserting into BST is done recursively.

Let the new node’s key be X,

o   Begin at root

o   If X is less than node’s key then insert X into left sub tree, otherwise insert X into right sub tree

o   Repeat until we found an empty node to put X (X will always be a new leaf)

-       Deletion

There are 3 cases which should be considered:

o   If the key is in a leaf, just delete that node

o   If the key is in a node which has one child, delete that node and connect its child to its parent

o   If the key is in a node which has two children, find the right most child of its left sub tree (node P), replace its key with P’s key and remove P recursively. (or alternately you can choose the left most child of its right sub tree)