Binary Search Trees | DSA in C++ - Software Development PDF Download

Introduction

Binary Search Trees (BSTs) are a fundamental data structure in computer science, particularly in algorithms and data structures. They provide an efficient way to store and search for data, making them essential in many applications. In this article, we will explore the basics of Binary Search Trees, their properties, and how to implement and utilize them in C++. We will also provide multiple examples and simple code snippets with explanations to help you understand the concepts better.

What is a Binary Search Tree?

Properties of Binary Search Trees

• The left subtree of a node contains values smaller than the node's value.
• The right subtree of a node contains values greater than the node's value.
• The BST does not contain duplicate values.
• The inorder traversal of a BST results in a sorted sequence of values.

Implementing Binary Search Trees in C++

To implement a Binary Search Tree in C++, we can define a struct or a class to represent the nodes. Each node contains a value and pointers to its left and right children.

struct Node {

    int data;

    Node* left;

    Node* right;

};

Searching in a Binary Search Tree

Searching for a value in a Binary Search Tree involves comparing the value with the current node and recursively searching in the left or right subtree based on the comparison.

bool search(Node* root, int value) {

    if (root == nullptr)

        return false;

    if (root->data == value)

        return true;

    if (value < root->data)

        return search(root->left, value);

    else

        return search(root->right, value);

}

Insertion in a Binary Search Tree

Inserting a value in a Binary Search Tree follows a similar recursive approach. We compare the value with the current node and decide whether to insert it in the left or right subtree. If the appropriate child is empty, we create a new node and assign it as the child.

Node* insert(Node* root, int value) {

    if (root == nullptr) {

        Node* newNode = new Node;

        newNode->data = value;

        newNode->left = nullptr;

        newNode->right = nullptr;

        return newNode;

    }

    if (value < root->data)

        root->left = insert(root->left, value);

    else if (value > root->data)

        root->right = insert(root->right, value);

    return root;

}

Deletion in a Binary Search Tree

Deleting a node from a Binary Search Tree can be a bit more complex. We need to consider various cases based on the node's children. The process involves finding the node to be deleted, handling the cases accordingly, and rearranging the tree.

(Note: Detailed explanation of deletion is omitted for brevity. Refer to specialized resources for a comprehensive understanding.)

Traversing a Binary Search Tree

There are three common ways to traverse a Binary Search Tree: inorder, preorder, and postorder. Inorder traversal visits the nodes in ascending order.

void inorderTraversal(Node* root) {

    if (root == nullptr)

        return;

    inorderTraversal(root->left);

    cout << root->data << " ";

    inorderTraversal(root->right);

}

Sample Problems and Solutions

Problem 1: Given a Binary Search Tree, find the maximum value in the tree.

int findMaxValue(Node* root) {

    if (root == nullptr)

        throw logic_error("Tree is empty");

    while (root->right != nullptr)

        root = root->right;

    return root->data;

}

Problem 2: Given a Binary Search Tree, check if it is a valid BST.

bool isValidBST(Node* root, int minVal, int maxVal) {

    if (root == nullptr)

        return true;

    if (root->data <= minVal || root->data >= maxVal)

        return false;

    return isValidBST(root->left, minVal, root->data) &&

           isValidBST(root->right, root->data, maxVal);

}

Conclusion

Binary Search Trees are powerful data structures that enable efficient searching, insertion, and deletion operations. By following the properties and principles discussed in this article, you can effectively utilize Binary Search Trees to solve a wide range of problems. With the provided examples and code snippets, you should now have a good foundation to explore further and apply Binary Search Trees in your own projects.