All about Binary Search Trees

UPDATES:

---

• Added a new problem (prob. 7)
• Added a new traversal technique

CONTENTS:

---

1. Insertion in a BST.
2. Tree traversal techniques.
3. Height of Binary Search Tree.
4. Validating a BST.
5. Finding the Lowest Common Ancestor of key1 and key2 in BST.
6. Deletion of a node 'N' from BST.
7. Finding maximum (or minimum) in path from node A to node B.

What is a binary search tree ?

---

Binary Search Tree, is a node-based binary tree data structure having the following properties:

• The left subtree of a node contains only nodes with keys less 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.

---

Most of operations on binary search trees like insertion, deletion, search etc can be done in logarithmic time O(logN).
Let's discuss each of them in detail.
First of all lets see the Structure of binary search tree :

1. Insertion : insert(root, key) : Starting with root node keep on comparing key with the value of nodes of Binary Search Tree recursively with two conditions :
   • If value of key is greater than current node : move to its right subtree
   • otherwise : move to its left subtree
   Remember : New nodes are always inserted as the leaf nodes of Binary Search tree.
   Practice On Hackerrank

   ---

2. Four types of tree traversal techniques :
   
   1. Pre-order tree traversal : Follow this order : root --- left --- right
      It means that we need to first print the data of current node, then we have to move to its left subtree and then its right subtree recursively.
   2. In-order tree traversal : Follow this order : left --- root --- right
      In inorder traversal we first need to visit its left subtree and after printing its left subtree we print the current node data and then print its right subtree recursively. This traversal will print all the nodes of tree in ascending order.
   3. Post-order tree traversal : Follow this order : left --- right --- root
      In postorder traversal we first need to visit its left subtree and after printing its left subtree we print its right subtree recursively and then the value of current node recursively.
   4. Level Order Traversal :
      It is easy to implement if you know BFS algorithm. Before learning this you must learn BFS graph traversal algorithm.
      Now make a queue and insert root in it. Then print it out and pop it from queue and insert its left child first and then right child into the queue. Then do the same for each node until queue is not empty.
      
3. Height of Binary Search Tree : Height is defined as the number of nodes in the longest path from the root node to a leaf node.
   StackOverflow : finding height of a BST
4. Check if a tree is BST or not ? : Use an awesome property of BST : Inorder traversal of BST prints data in ascending order.
5. Finding the Lowest Common Ancestor of key1 and key2 in BST :
   The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in BST that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).
   Consider 3 cases :
   • Both key1 and key2 are on left side of a node.
   • Both key1 and key2 are on right side of a node.
   • One is on left side and other is on right side.
6. Deletion of a node 'N' from BST : Lets consider some cases which are necessary to consider while deleting a node :
   • if left child of N is NULL : replace node N with its right child.
   • if right child of N is NULL : replace node N with its left child.
   • if none of child of N is NULL : we have 2 choices :
     1. replace it with minimum value node in its right subtree.
     2. or replace it with maximum value node in its left subtree.
7. UPD1 : Finding maximum (or minimum) in path from node A to node B :
   Link for practice @Hackerearth

   ---

   So after reading about LCA(lowest common ancestor) in point 5, we can easily find it for given 2 nodes. But why LCA ? See. we can easily reach both nodes from LCA by just moving to left or right child recursively but to move from one node to other is difficult if they are in different subtrees without knowing their LCA. So LCA helps us here !
   Now find max in path from LCA to node A. Lets call it ans1
   Similarly find max in path from LCA to node B. Lets call it ans2
   Finally your answer must be max(ans1, ans2) .

So i hope after reading this you have gained a lot of knowledge about Binary search trees and their implementation in C++.
If you have any doubt about BST you can ask freely and if you find it useful please give your feedback in the comment section.
Happy Coding !