Why BST Over Plain Binary Tree in DSA C++ - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of numbers and you want to find, add, or check if a number exists quickly. You can organize these numbers in a tree structure. A plain binary tree just puts numbers anywhere, but a Binary Search Tree (BST) keeps them in order. This project will help you see why BST is better for searching.

🎯 Goal: You will build a simple binary tree and a binary search tree with the same numbers. Then, you will search for a number in both trees and see the difference in how they work.

📋 What You'll Learn

Create a plain binary tree with specific numbers

Create a binary search tree with the same numbers

Write a function to search a number in the plain binary tree

Write a function to search a number in the BST

Print the search results for both trees

💡 Why This Matters

🌍 Real World

Organizing data so you can find things quickly is important in many apps like phone contacts or product catalogs.

💼 Career

Understanding BST helps in software development roles where efficient data searching and storage is needed.

1

Create a plain binary tree with nodes 10, 5, 15

Create a struct called Node with an int data, and two pointers left and right. Then create three nodes with values 10, 5, and 15. Connect them so that 10 is the root, 5 is the left child, and 15 is the right child.

DSA C++

// Define struct Node
// Create nodes root, leftChild, rightChild
// Connect nodes to form the tree

Hint

Think of Node as a box holding a number and two pointers to other boxes.

2

Create a function to search a number in the plain binary tree

Add a function called searchPlain that takes a Node* and an int key. It should return true if the key is found anywhere in the tree by checking the current node and recursively searching left and right children.

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

bool searchPlain(Node* root, int key) {
    // Your code here
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};

    root->left = leftChild;
    root->right = rightChild;

    return 0;
}

Hint

Check if the current node matches the key. If not, search left and right children.

3

Create a function to search a number in the binary search tree (BST)

Add a function called searchBST that takes a Node* and an int key. It should return true if the key is found by using the BST property: if key is less than current node's data, search left; if greater, search right; if equal, return true.

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

bool searchPlain(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == key) {
        return true;
    }
    return searchPlain(root->left, key) || searchPlain(root->right, key);
}

bool searchBST(Node* root, int key) {
    // Your code here
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};

    root->left = leftChild;
    root->right = rightChild;

    return 0;
}

Hint

Use the rule: go left if key is smaller, right if bigger, stop if equal.

4

Print search results for key 15 in both trees

In main(), call searchPlain(root, 15) and searchBST(root, 15). Print "Found in plain tree" if searchPlain returns true, else "Not found in plain tree". Similarly, print "Found in BST" or "Not found in BST" based on searchBST result.

DSA C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
};

bool searchPlain(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == key) {
        return true;
    }
    return searchPlain(root->left, key) || searchPlain(root->right, key);
}

bool searchBST(Node* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == key) {
        return true;
    } else if (key data) {
        return searchBST(root->left, key);
    } else {
        return searchBST(root->right, key);
    }
}

int main() {
    Node* root = new Node{10, nullptr, nullptr};
    Node* leftChild = new Node{5, nullptr, nullptr};
    Node* rightChild = new Node{15, nullptr, nullptr};

    root->left = leftChild;
    root->right = rightChild;

    // Call searchPlain and searchBST for key 15
    // Print results accordingly
}

Hint

Use if statements to check the return values and print the messages.