In this blog post will study what is are binary search trees, applications, operations and C++ code implementation for BST.

Defintion

Applications

• Used for indexing and multi-indexing.
• Used to implement various sorting algorigthms.
• TreeMap and TreeSet data structures are internally implemented using self-balancing BSTs.
• The inOrder traversal itself gives the sorted order of the elements in BST.

Standard Operations

Do refer the code available the end of this section to understand the following thoery.

1. Traversal:
   1. Inorder Traversal(Left,Root,Right): Traverse the left sub-tree in Inorder, Visit the Root, Traverse the right sub-tree in Inorder.
   2. Postorder Traversal(Left,Right,Root): Traverse the left sub-tree in Postorder, Traverse the right sub-tree in Postorder, Visit the Root.
   3. Preorder Traversal(Root,Left,Right): Visit the Root, Traverse the left sub-tree in Preorder, Traverse the right sub-tree in Preorder.
2. Insertion: If root is null then return the new node. Else assign root to a temporary variable called child node and keep a pointer to refer the parent node.
   Loop until child node is not NULL. First assign child node to previous node and then compare the values of child node and new node.
   If child node's value is greater than new node's value then assign child node's left pointer to child node(traverse left sub-tree). Else assign child node's right pointer to child node(traverse right sub-tree).
   After looping, if previous node's value is greater than new node's value then assign previous node's left pointer to new node else assign right pointer to new node.
3. Search: If root's data is equal to data to be searched then return root.
   If root's data is greater than data to be searched then traverse left sub-tree.
   If root's data is smaller than data to be searched then traverse right sub-tree.
4. Deletion: If root's data is equal to data to be deleted and root has child nodes then we can't perform delete operation. If root's data is equal to data to be deleted and root has no child nodes then assign NULL value to root and return.
   Else find the node to be deleted and it's parent using search operation. If it is a leaf node then check whether this node is parent's left or right child and assign NULL to that particular pointer of parent's node.
   Else if the node isn't a leaf and has only one child then check which child(either left or right) node exists and assign that to parent's left or right node(depending on whether the node to be deleted is parent's left or right child).
   Else if the node isn't a leaf and has both the child then find the inorder successor(minimum value in right sub-tree) of the node to be deleted. Assign it's value to the node to be deleted and delete the inorder successor.
   

   Deletion operation sounds clumsy but it's easy once understood the coding part.

Similar posts: Tree Data Structure | Binary Trees | Binary Heap