Binary Search Tree, Code ↔ Language

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 initialize data with val, and left and right with nullptr.
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 to nullptr, indicating an empty tree.

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 new Node 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.
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.

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.
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.

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 is nullptr (i.e., if the tree or subtree is empty), the height is 0. This is because an empty tree has no nodes, and hence its height is considered 0.
- 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 and rightHeight) plus 1. The +1 accounts for the current node.
- The result is the height of the subtree rooted at the current node.

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.
In the private section:
- Helper Function depth(Node* node, int value)
  - Base Case (Node is nullptr):
  - If the node is nullptr (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 the value, the function returns 0 because the node itself is at depth 0.
  - 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.

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.
Private Method search(Node* node, int value)
- This recursive helper function searches for a value in the subtree rooted at node.
- Base Case:
- If node is nullptr (i.e., if the subtree is empty), the function returns false, indicating that the value is not found in this path.
- Value Found Case:
- If node->data is equal to the value, the function returns true, indicating that the value has been found.
- Recursive Case:
- If the value is less than node->data, the function recursively searches in the left subtree by calling itself with node->left.
- If the value is greater than node->data, the function recursively searches in the right subtree by calling itself with node->right.
- The function returns true if the value is found in either subtree, or false if it is not found in either.

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.
Private Method deleteNode(Node* node, int value)
- This recursive helper function deletes a value from the subtree rooted at node.
- Base Case:
- If node is nullptr, it returns nullptr, indicating that the value was not found in this path.
- Traversal Case:
- If value is less than node->data, the function recursively deletes the value from the left subtree.
- If value is greater than node->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.
- The function returns the potentially modified subtree after deletion.
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.

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;
    }
};