A Binary Search Tree is binary tree which is either empty or a node having a key value, left child & right child.
By analyzing the above definition, we notice that BST comes into two variants namely empty BST & non-empty BST.
The empty BST contain no added structure, whereas the non-empty BST contain three components.
The non-empty BST satisfies the given conditions:
a) The key within the left child of node (if exists) is less than the key in its parent node.
b) The key within the right child of a node (if exists) is greater than the key in its parent node.
c) The left & right sub trees of the root are binary search trees again.
The given are some operations which can be performed on Binary search trees:
- formation of an empty tree
- Traversing the BST
- Counting internal nodes (non-leaf nodes)
- Counting external nodes (leaf nodes)
- Counting total number of nodes
- Determining the height of tree
- Insertion of a new node
- Searching for an element
- Determination smallest element
- determination largest element
- Deletion of a node.