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.

Operations in an BST:

1. Insertion in BST:
2. Searching in BST:
3. Deletion in BST:

4.1 Insertion in BST:

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree:

• Check the value to be inserted (say X) with the value of the current node (say val) we are in:
  • If X is less than val move to the left subtree.
  • Otherwise, move to the right subtree.
• Once the leaf node is reached, insert X to its right or left based on the relation between X and the leaf node’s value.

Time Complexity: O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to travel from the root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of insertion operation may become O(n). 
Auxiliary Space: O(1), if we use a iterative approach, and (n), as we use recursive approach.

4.2 Searching in BST:

For searching a value in BST, consider it as a sorted array. Now we can easily perform search operation in BST using Binary Search Algorithm. Let’s say we want to search for the number X, We start at the root. Then:

• We compare the value to be searched with the value of the root. 
  • If it’s equal we are done with the search if it’s smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger. 
• Repeat the above step till no more traversal is possible
• If at any iteration, key is found, return True. Else False.

Time Complexity: O(h), where h is the height of the BST.
Auxiliary Space:The auxiliary space complexity of searching in a binary search tree is O(1) if we use a iterative approach, and (n), as we use recursive approach.

4.3 Deletion in BST:

The task to delete a node in this BST, can be broken down into 3 scenarios:

Case 1. Delete a Leaf Node in BST

If the node to be deleted is a leaf node, it can simply be removed from the tree. The parent node of the deleted node must have its corresponding child pointer set to NULL to reflect the change in the tree.

Case 2. Delete a Node with Single Child in BST

If the node to be deleted has only one child, the child can be promoted to replace the deleted node. The parent node of the deleted node must have its corresponding child pointer updated to point to the promoted child.

Case 3. Delete a Node with Both Children in BST

If the node to be deleted has two children, the replacement node can be found by either selecting the minimum value from the right subtree or the maximum value from the left subtree of the node to be deleted. After finding the replacement node, it can be promoted to replace the deleted node. The left subtree of the replacement node (if it exists) must be attached to the left child of the promoted node, and the right subtree of the replacement node (if it exists) must be attached to the right child of the promoted node. The parent node of the deleted node must have its corresponding child pointer updated to point to the promoted node.

Time Complexity: O(h), where h is the height of the BST. 
Auxiliary Space: O(n).

Trees are foundational structures in computer science, serving as the backbone for numerous algorithms and data representations. GATE aspirants should be well versed in tree structures to prepare for the GATE Exam in 2024. This article aims to provide a concise yet comprehensive overview of trees, exploring key concepts crucial for a comprehensive understanding of the topic. To help candidates understand tree-based problem-solving scenarios, these notes provide invaluable insights and knowledge essential to success in GATE.