What is a binary search tree?

A binary tree T is a binary search tree if it satisfies the following conditions:

1. T is an empty tree (represented by a null pointer), or
2. 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 

// 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 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 data) {
            return searchRecursive(current->left, value);
        } else {
            return searchRecursive(current->right, value);
        }
    }

    void inorderTraversalRecursive(Node* current) {
        if (current != nullptr) {
            inorderTraversalRecursive(current->left);
            std::cout data 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 
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.
Related Articles
استكشف أفضل كتب انجل…
A List of the Best College Graduation…
10 Eye-catching Strategy Games You Ne…
Key Tips for Renting an Electric Vehi…
Revive Your Morning: NAC Hangover Cur…

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.
The post An Implementation of a Binary Search Tree (BST) in C++ first appeared on Game Space.