Binary Search Tree
Binary Search Tree, 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.
- There must be no duplicate nodes.
Traversal
Inorder traversal in BST will be in ascending order. Therefore, the inorder traversal is the most frequent used traversal method of a BST.
Inorder Successor
Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.
In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.
*Delete O(h)
When we delete a node, there possibilities arise.
- Node to be deleted is leaf: Simply remove from the tree.
- Node to be deleted has only one child: Copy the child to the node and delete the child
- Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
The important thing to note is, inorder successor is needed only when right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in right child of the node.
Time Complexity
The strength of a BST is that you can perform all search, insertion and deletion operations in O(h) time complexity even in the worst case.
The height of a skewed tree may become n and the time complexity of delete operation may become O(n)