What is Binary Search Tree ?
In Data structures, a binary search tree is a linked data structure that provides a way to store data orderly. All stored keys should satisfy the properties of a Binary search tree. These properties are:
- Nodes of right subtree always have a value greater than the parent’s node
- Nodes of left subtree always have value lesser than the parent’s node
It requires O(log n) time to perform basic operations in the average case. However, basic operations on BST take time proportional to the height of the tree.
Each node represents an object that consists link to the right subtree, a key value associated with the node, and a link to left subtree. If any parent or child node is missing, then it would be represented as NIL value.
Binary search tree supports operations such as Insertion, Deletion, Searching of a node in the tree and also allow us to find Minimum, Maximum, Successor and Predecessor. Apart from that, a BST can be traversed in three-ways Inorder traversal, post-order traversal, and pre-order traversal.
Basic Operations in Binary Search Tree
Search Operation
A search operation starts from the root node to all the way downward recursively. The targeted element is compared with the root node, if both are equal then the search would get terminated.
If it is smaller than the root node then the search goes on at left subtree. And if the targeted value is greater, then search operation would be performed left subtree recursively.
Insertion and deletion
To insert a given element, BST first performs search operation, starting from the root node in order to locate the insertion position. Ones a NIL location is found then insertion is performed.
To delete a key from a BST we must know three cases:
1) If the targeted element has no child then remove the element and place NIL.
2) If the targeted element has only a single child, in this case, we just fill that place by simply putting its child node in its position.
3) If it has two children, then the key greater then the targeted value or Successor of targeted value would replace it.
Minimum and Maximum
A minimum key in a BST can be figured out by traversing left subtree from root node till a NIL is not encountered.
Similarly, A maximum key in a BST can be figured out by traversing right subtree from root node till a NIL is not encountered.
Successor and predecessor
A successor node for a given key value of BST can be derived without performing any comparison. If there is an immediate key available which is greater than the given node then the value would be returned otherwise NIL would be returned.
A predecessor node for a given key value of BST can be derived, if there is an immediate key smaller than given node then the value would be returned otherwise NIL.
Traversal
Traversing refers to visit each and every node of a tree. Binary search tree can be traversed in three ways
In-order traversal
In this way of traversing a tree, we start from visiting all the nodes of left subtree, then root and then lastly right subtree
Pre-order traversal
In this way of traversing a tree, we start from the root, then visit all the nodes of left subtree and then last traverse right subtree
Post-order traversal
In this way of traversing a tree, we start from visiting all the nodes of left subtree, then all the nodes of the right subtree and then lastly root
