Creation of Binary Search Tree (Linked List Implementation)
class BinarySearchTree {
private:
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = nullptr;
right = nullptr;
}
};
Node* root;
public:
// Constructor to initialize the Binary Search Tree
BinarySearchTree() {
root = nullptr;
}
};
First, we will create a class named
BinarySearchTree
.-
It will contain a
struct Node
with the following properties:-
int data
: Stores the value of the node. -
Node* left
: Points to the left child node. -
Node* right
: Points to the right child node. -
Node(int val)
: Constructor to initializedata
withval
, andleft
andright
withnullptr
.
-
-
It will contain a property
root
:-
Node* root
: Points to the root node of the binary search tree.
-
-
We will declare a constructor
BinarySearchTree()
:- It will initialize the
root
pointer tonullptr
, indicating an empty tree.
- It will initialize the
Insertion Operation
private:
// Helper function to insert a value into the tree
Node* insert(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
public:
// Public method to insert a value into the tree
void insert(int value) {
root = insert(root, value);
}
We will define the insertion operation as follows:
-
In the
private
section:-
Helper Function
insert(Node* node, int value)
- This recursive function handles the insertion of a value into the binary search tree.
- If the current node is
nullptr
, it creates a newNode
with the given value and returns it. - If the value to be inserted is less than the current node’s data, it recursively inserts the value into the left subtree.
- If the value is greater than the current node’s data, it recursively inserts the value into the right subtree.
- Finally, it returns the updated node.
-
Helper Function
-
In the
public
section:-
Public Method
insert(int value)
- This method is used to insert a value into the binary search tree.
- It calls the helper function
insert
with the root of the tree and the value to be inserted.
-
Public Method
Preorder Traversal
private:
// Helper function for preorder traversal
void preorderTraversal(Node* node) {
if (node == nullptr) {
return;
}
cout << node->data << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
public:
// Public method to start preorder traversal
void preorder() {
preorderTraversal(root);
}
We will define the preorder traversal operation as follows:
-
In the
private
section:-
Helper Function
preorderTraversal(Node* node)
- This recursive function handles the preorder traversal of the binary search tree.
- If the current node is
nullptr
, it returns immediately, as there are no nodes to process. - It prints the data of the current node.
- It then recursively performs preorder traversal on the left subtree.
- It recursively performs preorder traversal on the right subtree.
-
Helper Function
-
In the
public
section:-
Public Method
preorder()
- This method is used to start the preorder traversal from the root of the tree.
- It calls the helper function
preorderTraversal
with the root of the tree.
-
Public Method
Level Order Traversal
public:
// Public method to perform level order traversal
void levelOrder() {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->data << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
We will define the level order traversal operation as follows:
-
Public Method
levelOrder()
- This method performs a level order traversal (also known as breadth-first traversal) of the binary search tree.
- It first checks if the root is
nullptr
; if so, it returns immediately. - It uses a queue to keep track of nodes at each level.
- It starts by pushing the root node into the queue.
- While the queue is not empty:
- It dequeues a node and prints its data.
- It enqueues the left child of the node if it is not
nullptr
. - It enqueues the right child of the node if it is not
nullptr
.
Height of the Tree
public:
// Public method to calculate the height of the tree
int height() {
return height(root);
}
private:
// Helper function to calculate the height of the tree
int height(Node* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return max(leftHeight, rightHeight) + 1;
}
We will define the height calculation for the binary search tree as follows:
-
Public Method
height()
- This method provides a public interface to calculate the height of the entire tree.
- It calls the private helper function
height(Node* node)
starting with the root node. - The method returns the result of the helper function, which is the height of the tree.
-
Private Method
height(Node* node)
- This recursive helper function calculates the height of the subtree rooted at
node
. -
Base Case: If the
node
isnullptr
(i.e., if the tree or subtree is empty), the height is0
. This is because an empty tree has no nodes, and hence its height is considered0
. - Recursive Case:
- The function calculates the height of the left subtree by calling itself with
node->left
. - It calculates the height of the right subtree by calling itself with
node->right
. - It then returns the maximum of the two heights (
leftHeight
andrightHeight
) plus1
. The+1
accounts for the current node. - The result is the height of the subtree rooted at the current node.
- This recursive helper function calculates the height of the subtree rooted at
Depth of a Node
public:
// Public method to calculate the depth of a specific node
int depth(int value) {
return depth(root, value);
}
private:
// Helper function to calculate the depth of a node with a specific value
int depth(Node* node, int value) {
if (node == nullptr) {
return -1; // Node not found, return -1
}
if (node->data == value) {
return 0; // Node found, depth is 0 (current node)
}
// Recursively search for the node in the left or right subtree
int leftDepth = depth(node->left, value);
int rightDepth = depth(node->right, value);
if (leftDepth == -1 && rightDepth == -1) {
return -1; // Node not found in either subtree
}
// Return the depth if the node is found in one of the subtrees
return max(leftDepth, rightDepth) + 1;
}
Explanation:
-
In the
public
section:-
Public Method
depth(int value)
- This method provides a public interface to calculate the depth of a specific node identified by
value
. - It calls the private helper function
depth(Node* node, int value)
starting with the root node. - The method returns the result of the helper function, which is the depth of the node with the given value.
- This method provides a public interface to calculate the depth of a specific node identified by
-
Public Method
-
In the
private
section:-
Helper Function
depth(Node* node, int value)
-
Base Case (Node is
nullptr
): - If the
node
isnullptr
(i.e., the subtree is empty or the node does not exist), the function returns-1
to indicate that the node was not found. - Node Found:
- If
node->data
matches thevalue
, the function returns0
because the node itself is at depth0
. - Recursive Case:
- The function recursively searches for the node in the left subtree by calling
depth(node->left, value)
. - It also recursively searches for the node in the right subtree by calling
depth(node->right, value)
. - Check Node Existence:
- If the node is not found in either subtree (
leftDepth == -1 && rightDepth == -1
), the function returns-1
indicating that the node does not exist. - Return Depth:
- If the node is found in one of the subtrees, the function returns the maximum depth from the left or right subtree plus
1
. The+1
accounts for the current node level. - This calculation ensures that the depth returned represents the distance from the root to the node with the specified value.
-
Base Case (Node is
-
Helper Function
Searching Operation
public:
// Public method to search for a value in the tree
bool search(int value) {
return search(root, value);
}
private:
// Helper function to search for a value in the subtree rooted at node
bool search(Node* node, int value) {
if (node == nullptr) {
return false; // Value not found
}
if (node->data == value) {
return true; // Value found
}
if (value < node->data) {
return search(node->left, value); // Search in the left subtree
} else {
return search(node->right, value); // Search in the right subtree
}
}
We will define the search functionality for the binary search tree as follows:
-
Public Method
search(int value)
- This method provides a public interface to search for a specific
value
in the tree. - It calls the private helper function
search(Node* node, int value)
starting with the root node. - The method returns the result of the helper function, which is a boolean indicating whether the value is present in the tree.
- This method provides a public interface to search for a specific
-
Private Method
search(Node* node, int value)
- This recursive helper function searches for a
value
in the subtree rooted atnode
. - Base Case:
- If
node
isnullptr
(i.e., if the subtree is empty), the function returnsfalse
, indicating that the value is not found in this path. - Value Found Case:
- If
node->data
is equal to thevalue
, the function returnstrue
, indicating that the value has been found. - Recursive Case:
- If the
value
is less thannode->data
, the function recursively searches in the left subtree by calling itself withnode->left
. - If the
value
is greater thannode->data
, the function recursively searches in the right subtree by calling itself withnode->right
. - The function returns
true
if the value is found in either subtree, orfalse
if it is not found in either.
- This recursive helper function searches for a
Deletion Operation
public:
// Public method to delete a value from the tree
void deleteValue(int value) {
root = deleteNode(root, value);
}
private:
// Helper function to delete a value from the subtree rooted at node
Node* deleteNode(Node* node, int value) {
if (node == nullptr) {
return nullptr; // Value not found
}
// Traverse the tree to find the node to delete
if (value < node->data) {
node->left = deleteNode(node->left, value); // Go left
} else if (value > node->data) {
node->right = deleteNode(node->right, value); // Go right
} else {
// Node with the value to be deleted found
// Case 1: Node with only one child or no child
if (node->left == nullptr) {
Node* temp = node->right;
delete node; // Free memory
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node; // Free memory
return temp;
}
// Case 2: Node with two children
Node* temp = minValueNode(node->right); // Get the in-order successor
node->data = temp->data; // Copy the in-order successor's value to this node
node->right = deleteNode(node->right, temp->data); // Delete the in-order successor
}
return node;
}
// Helper function to find the node with the minimum value in the subtree
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left != nullptr) {
current = current->left; // Traverse to the leftmost leaf
}
return current;
}
We will define the deletion functionality for the binary search tree as follows:
-
Public Method
deleteValue(int value)
- This method provides a public interface to delete a specific
value
from the tree. - It calls the private helper function
deleteNode(Node* node, int value)
starting with the root node. - The method updates the
root
with the result of the helper function after the deletion process.
- This method provides a public interface to delete a specific
-
Private Method
deleteNode(Node* node, int value)
- This recursive helper function deletes a
value
from the subtree rooted atnode
. - Base Case:
- If
node
isnullptr
, it returnsnullptr
, indicating that the value was not found in this path. - Traversal Case:
- If
value
is less thannode->data
, the function recursively deletes the value from the left subtree. - If
value
is greater thannode->data
, the function recursively deletes the value from the right subtree. - Node Found Case:
-
Case 1: Node with Only One Child or No Child
- If the node to be deleted has no left child, it returns the right child, effectively bypassing the node.
- If the node to be deleted has no right child, it returns the left child, effectively bypassing the node.
-
Case 2: Node with Two Children
- It finds the in-order successor (the smallest node in the right subtree) using the
minValueNode
function. - It replaces the value of the node to be deleted with the in-order successor’s value.
- It then recursively deletes the in-order successor from the right subtree.
- It finds the in-order successor (the smallest node in the right subtree) using the
- The function returns the potentially modified subtree after deletion.
- This recursive helper function deletes a
-
Private Method
minValueNode(Node* node)
- This helper function finds and returns the node with the minimum value in the subtree rooted at
node
. - It traverses the leftmost path to find the smallest node.
- This helper function finds and returns the node with the minimum value in the subtree rooted at
Full Code Implementation
class BinarySearchTree {
private:
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = nullptr;
right = nullptr;
}
};
Node* root;
public:
BinarySearchTree() {
root = nullptr;
}
void insert(int value) {
root = insert(root, value);
}
void preorder() {
preorderTraversal(root);
}
void levelOrder() {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front();
q.pop();
cout << node->data << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
int height() {
return height(root);
}
int depth(int value) {
return depth(root, value);
}
bool search(int value) {
return search(root, value);
}
void deleteValue(int value) {
root = deleteNode(root, value);
}
private:
Node* insert(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
void preorderTraversal(Node* node) {
if (node == nullptr) {
return;
}
cout << node->data << " ";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
int height(Node* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return max(leftHeight, rightHeight) + 1;
}
int depth(Node* node, int value) {
if (node == nullptr) {
return -1;
}
if (node->data == value) {
return 0;
}
int leftDepth = depth(node->left, value);
int rightDepth = depth(node->right, value);
if (leftDepth == -1 && rightDepth == -1) {
return -1;
}
return max(leftDepth, rightDepth) + 1;
}
bool search(Node* node, int value) {
if (node == nullptr) {
return false;
}
if (node->data == value) {
return true;
}
if (value < node->data) {
return search(node->left, value);
} else {
return search(node->right, value);
}
}
Node* deleteNode(Node* node, int value) {
if (node == nullptr) {
return nullptr;
}
if (value < node->data) {
node->left = deleteNode(node->left, value);
} else if (value > node->data) {
node->right = deleteNode(node->right, value);
} else {
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp;
}
Node* temp = minValueNode(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
}
return node;
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left != nullptr) {
current = current->left;
}
return current;
}
};
Top comments (0)