Binary Search Tree 101

                           On the previous post, we have already discussed about the concept of Hasing Table, Tree and Binary, all related problems, steps on how to encounter them, along with their examples. Now we are going to continue with our next discussion topic regarding the concept of Binary Search Tree, the sorted versions of binary tree. In order to cover the basics, let us jump into the discussion.

Binary Search Tree
                            Data structures that supports faster searching, rapid sorting, and easy insertion and deletion.

•         The Concept           
• For a node x in of a BST T:
• Left subtree of x contains smaller elements than those stored in x.
• Right subtree of x contains all greater elements than those stored in x.

                                                              *assume the keys are unique

•         The Operations           
• find(x): find key x in the BST.
• Assume the key to be searched is X:
• Start from root
• Terminates successfully if root contains X
• Search recursively on left sub tree if X is less than root's key
• Search recursively on right sub tree if X is greater than root's key

• insert(x): insert new key x into BST.
• Assume the new node's key is X:
• Start from root
• Insert X to the left sub tree if X is less than node's key
• Insert X to the right sub tree if X is greater than node's key
• Repeat until new Leaf for X is found

• remove(x): remove key x from BST.
• 3 cases should be considered:
• Delete node if key is in Leaf
• Delete node and connect its child to its parent if key is in a node with one child
• If key is in node with two children, find the right most child of its left sub tree (node P), replace its key with P's key and recursively remove P

That is all the basics about Binary Search Tree, the operations and things to be considered while using Binary Search Tree.

                                                                           - END -

References:

S. Sridhar. 2015. Design and Analysis of Algorithms. Oxford University Press. New Delhi. ISBN: 9780198093695. Chapter 6

Reema Thareja. 2014. Data structures using C. Oxford University Press. New Delhi. ISBN:9780198099307. Chapter 10

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein. (2009). Introduction to Algorithms. 03. The MIT Press. London. ISBN: 9780262033848. Chapter 12

Binary Search Tree, https://visualgo.net/bn/bst?slide=1 

https://www.geeksforgeeks.org/binary-search-tree-data-structure/