Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jul 17, 2024
Difficulty: Easy

Binary Search Trees

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

A binary Search Tree is a classification of Trees in which every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

Binary Search Trees

The properties that separate a binary search tree from a regular binary tree:

  • Order Property: In a BST, for each node, the left subtree contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key. This is not required for a regular binary tree.
  • No Duplicate Keys: Typically, BSTs do not allow duplicate keys. Each key must be unique and placed in a specific order as per the BST property. A regular binary tree can have duplicate keys.
  • Efficient Search Operations: Due to the ordered nature of a BST, search operations (as well as insertions and deletions) can be performed more efficiently, often in O(log n) time for balanced trees. Regular binary trees do not have this order, making search operations potentially less efficient, with a time complexity of O(n) in the worst case.

Lets us see an example of a binary search tree.

In this BST, we can observe that the left child of every node has a value less than its parent node, and the right child of every node has a value greater than its parent node.

Search Operation in Binary Search Tree

The search operation in a BST takes advantage of the tree's ordered structure. Starting at the root, the algorithm compares the target value to the current node's value. If they match, the search is successful. If the target is less than the current node's value, the algorithm recurses into the left subtree; if greater, it recurses into the right subtree. This process continues until the target is found or a leaf node is reached, indicating that the target is not in the tree.

Algorithm

  1. Start at the root node.
  2. If the root is None, the target is not in the tree.
  3. Compare the target value with the value of the current node:
    • If equal, the target is found.
    • If less, move to the left child and repeat the process.
    • If greater, move to the right child and repeat the process.
  4. If a leaf node is reached and the target is not found, the target is not in the tree.

Consider the following BST:

8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

To search for the value 7:

  1. Start at the root (8): 7 is less than 8, so move to the left child (3).
  2. At node 3: 7 is greater than 3, so move to the right child (6).
  3. At node 6: 7 is greater than 6, so move to the right child (7).
  4. At node 7: 7 is equal to 7, so the target is found.

Implementation

  • C
  • C++
  • Java
  • Python

C

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
int value;
struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int key) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->value = key;
newNode->left = newNode->right = NULL;
return newNode;
}

TreeNode* insert(TreeNode* node, int key) {
if (node == NULL) return createNode(key);

if (key < node->value)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node;
}

TreeNode* search(TreeNode* root, int key) {
if (root == NULL || root->value == key)
return root;

if (root->value < key)
return search(root->right, key);

return search(root->left, key);
}

int main() {
TreeNode* root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 4);
insert(root, 7);
insert(root, 14);
insert(root, 13);

int target = 7;
TreeNode* result = search(root, target);
if (result != NULL)
printf("Value %d found in the BST.\n", target);
else
printf("Value %d not found in the BST.\n", target);

return 0;
}

C++

#include <iostream>
using namespace std;

class TreeNode {
public:
int value;
TreeNode *left, *right;

TreeNode(int key) {
value = key;
left = right = nullptr;
}
};

TreeNode* insert(TreeNode* node, int key) {
if (node == nullptr) return new TreeNode(key);

if (key < node->value)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node;
}

TreeNode* search(TreeNode* root, int key) {
if (root == nullptr || root->value == key)
return root;

if (root->value < key)
return search(root->right, key);

return search(root->left, key);
}

int main() {
TreeNode* root = nullptr;
root = insert(root, 8);
insert(root, 3);
insert(root, 10);
insert(root, 1);
insert(root, 6);
insert(root, 4);
insert(root, 7);
insert(root, 14);
insert(root, 13);

int target = 7;
TreeNode* result = search(root, target);
if (result != nullptr)
cout << "Value " << target << " found in the BST." << endl;
else
cout << "Value " << target << " not found in the BST." << endl;

return 0;
}

Java

class TreeNode {
int value;
TreeNode left, right;

public TreeNode(int item) {
value = item;
left = right = null;
}
}

class BinarySearchTree {
TreeNode root;

TreeNode insert(TreeNode node, int value) {
if (node == null) {
node = new TreeNode(value);
return node;
}

if (value < node.value)
node.left = insert(node.left, value);
else if (value > node.value)
node.right = insert(node.right, value);

return node;
}

TreeNode search(TreeNode root, int key) {
if (root == null || root.value == key)
return root;

if (root.value < key)
return search(root.right, key);

return search(root.left, key);
}

public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();

tree.root = tree.insert(tree.root, 8);
tree.insert(tree.root, 3);
tree.insert(tree.root, 10);
tree.insert(tree.root, 1);
tree.insert(tree.root, 6);
tree.insert(tree.root, 4);
tree.insert(tree.root, 7);
tree.insert(tree.root, 14);
tree.insert(tree.root, 13);

int target = 7;
TreeNode result = tree.search(tree.root, target);
if (result != null)
System.out.println("Value " + target + " found in the BST.");
else
System.out.println("Value " + target + " not found in the BST.");
}
}

Python

class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.value = key

def search_bst(root, target):
if root is None or root.value == target:
return root

if target > root.value:
return search_bst(root.right, target)

return search_bst(root.left, target)

def insert(root, key):
if root is None:
return TreeNode(key)

if key < root.value:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)

return root

# Example usage
root = TreeNode(8)
root = insert(root, 3)
root = insert(root, 10)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 4)
root = insert(root, 7)
root = insert(root, 14)
root = insert(root, 13)

target = 7
result = search_bst(root, target)
if result:
print(f"Value {target} found in the BST.")
else:
print(f"Value {target} not found in the BST.")

Output

Value 7 found in the BST.

 

This code defines a TreeNode class and two functions: search_bst for searching a value in a BST, and insert for inserting new values into the BST. The example usage demonstrates creating a BST and searching for a value within it.

Now let us understand the procedure to insert and delete a node into the Binary Search Tree.

Inserting a node into Binary Search Tree 

Consider a Binary Search Tree ‘T’ and an arbitrary node ‘N’ having value stored as ‘Val’.  Below is the procedure to insert the node ‘N’ into ‘T’. 

  • First, we will compare the value ‘Val’ with the data stored in the root node. 
  • If ‘Val’ is greater than the root node's value, we will move to its right subtree.
  • If ‘Val’ is smaller than the root node's value, we will move to its left subtree.
  • We will repeat the first to third step until the current root node does not have left and right subtree. 
  • Now, if ‘Val’ is smaller than the value of the current root node, we will insert node ‘N’ as its left child.
  • Else if ‘Val’ is greater than the value of the current root node, we will insert node ‘N’ as its right child.

Now let us try inserting a node with ‘Val’ equal to 5 into the above tree.


Comparing the value ‘5’ from the value of the root and finding it to be greater, so moving to the right subtree. 

Comparing the value ‘5’ from the value of the current root and finding it to be smaller, so moving to the left subtree.

Comparing the value ‘5’ from the value of the current root and finding it to be greater, so moving to the right subtree.

On finding the current root without any subtree, we will insert the node ‘N’ as the right child.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Deleting a node from a Binary Search Tree

Let us consider a Binary Search Tree ‘T’ and the node to be deleted as ‘N’. Deletion of a node can be classified based on the number of children of the node to be deleted.  

1. ‘N’ has no children

When the node ‘N’ has no children, we can simply replace it will the null value.
For Example, the node with the value as ‘8’ is to be removed in the tree below.

Simply the node with the value ‘8’ can be removed.

2. ‘N’ has one child

When the node ‘N’ has only one child, we can replace it with its only child.
For Example, the node having the value as ‘4’ is removed in the below tree.

Simply the node with the value ‘4’ can be replaced with its only child, and then the replaced node will be removed.

3. ‘N’ has two children

When node ‘N’ has both children, we will need to determine the immediate predecessor. To find the immediate predecessor, we need to move to the left child of the node ‘N’ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor. 

Now this immediate predecessor can be replaced with the node ‘N’. And then, the replaced node can be removed with the first or second method defined above accordingly. 
For Example, the node with the value as ‘7’ is to be removed in the tree below.

We will have to find its immediate predecessor to replace it with. The node with the value ‘5’ is the immediate predecessor with the above algorithm. 

The node ‘N’ will be replaced with the immediate predecessor.

And then, the replaced node will be removed.

Frequently Asked Questions

How many maximum children can each Binary Search Tree node have?

The Binary Search Tree node can have a maximum of two children. The children are called left and right children.

What is the method to find the immediate predecessor?

To find the immediate predecessor, we need to move to the left child of the node ‘N’ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor. 

What is a key in a binary search tree?

A key in a binary search tree is the value stored in a node, used to organize and compare nodes according to the tree's ordering properties, ensuring that left children are smaller and right children are larger.

Why is it called a binary search tree?

It is called a binary search tree because it combines the properties of a binary tree (each node has at most two children) with the ability to perform efficient search operations, due to its ordered structure.

Conclusion

In the above article, we have learned about Binary Search Trees. Binary Search Trees (BSTs) are fundamental data structures that provide efficient means for data storage, retrieval, and management. By leveraging the ordered nature of BSTs, we can perform search, insert, and delete operations with optimal efficiency, making them a preferred choice for many applications.

Recommended problems -

Topics covered
1.
Search Operation in Binary Search Tree
1.1.
Algorithm
1.2.
Implementation
1.3.
C
1.4.
C++
1.5.
Java
1.6.
Python
2.
Inserting a node into Binary Search Tree 
3.
Deleting a node from a Binary Search Tree
3.1.
1. ‘N’ has no children
3.2.
2. ‘N’ has one child
3.3.
3. ‘N’ has two children
4.
Frequently Asked Questions
4.1.
How many maximum children can each Binary Search Tree node have?
4.2.
What is the method to find the immediate predecessor?
4.3.
What is a key in a binary search tree?
4.4.
Why is it called a binary search tree?
5.
Conclusion