Binary Search Tree (BST)

Question 1

What is a BST

Answer 1

Binary Search Tree is a data structure that has the following properties:

• The left sub-tree node has a key less than or equal to its parent’s node’s key
• The right sub-tree of a node has a key greater than to its parent’s node’s key
• subtree should also follow BST properties

Question 2

Why BST?

Answer 2

Operations like insertions, deletion, traversal, searching, takes O(n) in a Binary tree.
BST improve performance better than O(n)

Question 3

insertion in BST algorithm

Answer 3

function BST_insert(root, valueToInsert) {
	if (root === null) {
		// create a new node and insert
		root = newNode();
	} else if(valueToInsert < root) { 
		root.left = BST_insert(root.left, valueToInsert);
	} else {
		root.right = BST_insert(root.right, valueToInsert);
	}

return root; }

Question 4

deletion in BST algorithm

Answer 4

Deletion of node
Case 1: if a leaf node, then can be directly deleted
case 2: if a node to be deleted has 1 child. then connect the node to be deleted’s a child with the parent
case 3: if the node to be deleted has 2 children.
Find the successor of the root node, which is the least value node in the right subtree
replace node to be deleted need to be replaced with the successor

deleteNodeofBST(root, valueToBeDeleted) {
if (root = null) return null

	if (root < valueToBeDeleted) {
		root.left = deleteNodeofBST(root.left, valueToBeDeleted);
	} else if (root > valueToBeDeleted) {
		root.right = deleteNodeofBST(root.right, valueToBeDeleted);
	} else if(root === valueToBeDeleted) {
		// 3 cases
		if (!root.left &amp;&amp; !root.right){
		// if node to be deleted has no child
			root = null; 
		}
		else if (root.left &amp;&amp; root.right){
			 // if the root has both childs
			 // find the successor of right subtree 
			 // update root with successor node and delete the successor node from right tree
		} 
		else if(root.left &amp;&amp; !root.right)
		{
			// if node to be deleted has only left child
			root = root.left // connect the child with parent

		} else if(!root.left && root.right) {
			// if node to be deleted has only right child
			root = root.right // connect the child with parent
		}
		return root;
	}

}

Time complexity: O(log n)
Space complexity: O(log n)