What is a binary search tree?
A binary tree T is a binary search tree if it satisfies the following conditions:
- T is an empty tree (represented by a null pointer), or
- T consists of: a) A root node B with a value x, b) A left subtree L, which is also a binary search tree, where all elements in L have values less than x, and c) A right subtree R, which is also a binary search tree, where all elements in R have values greater than x.
An Implementation of a binary search tree in C++
#include <iostream> // Node class to represent each node in the binary search tree class Node { public: int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } }; // Binary Search Tree class class BST { private: Node* root; Node* insertRecursive(Node* current, int value) { if (current == nullptr) { return new Node(value); } if (value < current->data) { current->left = insertRecursive(current->left, value); } else if (value > current->data) { current->right = insertRecursive(current->right, value); } return current; } bool searchRecursive(Node* current, int value) { if (current == nullptr) { return false; } if (current->data == value) { return true; } if (value < current->data) { return searchRecursive(current->left, value); } else { return searchRecursive(current->right, value); } } void inorderTraversalRecursive(Node* current) { if (current != nullptr) { inorderTraversalRecursive(current->left); std::cout << current->data << " "; inorderTraversalRecursive(current->right); } } void deleteTree(Node* current) { if (current != nullptr) { deleteTree(current->left); deleteTree(current->right); delete current; } } public: BST() { root = nullptr; } ~BST() { deleteTree(root); } void insert(int value) { root = insertRecursive(root, value); } bool search(int value) { return searchRecursive(root, value); } void inorderTraversal() { inorderTraversalRecursive(root); std::cout << std::endl; } }; int main() { BST bst; // Inserting elements into the binary search tree bst.insert(10); bst.insert(5); bst.insert(15); bst.insert(2); bst.insert(7); // Performing in-order traversal of the tree std::cout << "In-order Traversal: "; bst.inorderTraversal(); // Searching for an element in the tree int searchValue = 7; if (bst.search(searchValue)) { std::cout << searchValue << " is found in the tree." << std::endl; } else { std::cout << searchValue << " is not found in the tree." << std::endl; } return 0; }
Node Class
The Node class represents each node in the binary search tree. It has three members: data, left, and right. The data member holds the value of the node, and left and right are pointers to the left and right child nodes, respectively.
If a node doesn’t have a left or right child, the corresponding pointer is set to nullptr.
Binary Search Tree (BST) Class
The BST class represents the binary search tree. It has a private member root, which is a pointer to the root of the tree. It is initialized to nullptr in the constructor, indicating an empty tree.
Insertion Operation
The insert() function is used to insert an element into the binary search tree. It takes an integer value as input, and it calls the private helper function insertRecursive() passing the root node and the value to be inserted.
The insertRecursive() function handles the recursive insertion of the value based on the binary search tree property.
If the value is less than the current node’s value, it is inserted in the left subtree; otherwise, it is inserted in the right subtree.
The function returns the modified node after insertion, and the updated root pointer is stored in the BST class.
Search Operation
The search() function is used to search for a specific value in the binary search tree. It takes an integer value as input and calls the private helper function searchRecursive() passing the root node and the value to be searched.
The searchRecursive() function handles the recursive search in the tree. If the current node is nullptr, it means the value is not found and returns false.
If the current node’s data matches the value, it returns true. Otherwise, it continues the search in the left or right subtree, depending on the value being less than or greater than the current node’s value.
In-order Traversal
The inorderTraversal() function performs an in-order traversal of the binary search tree.
In-order traversal visits the nodes in ascending order when the tree contains integer values. It calls the private helper function inorderTraversalRecursive() passing the root node to start the traversal.
The inorderTraversalRecursive() function performs a recursive traversal by visiting the left subtree, then the current node, and finally the right subtree. This results in an ordered list of values.
Destructor
The BST class also has a destructor ~BST(). It is responsible for freeing the memory allocated for the binary search tree when the BST object goes out of scope.
The destructor calls the private deleteTree() function, which recursively traverses the tree and deallocates the memory for each node.
Main Function
In the main() function, we create a BST object named bst. Then we insert elements (10, 5, 15, 2, 7) into the binary search tree using the insert() method.
After that, we perform an in-order traversal using inorderTraversal() to see the elements in ascending order. Finally, we search for an element (7 in this case) using the search() method and print whether it’s found or not.
The output of the program will show the in-order traversal result and indicate whether the value 7 is found in the tree or not.