BST Search Operation in DSA C++ - Build from Scratch

BST Search Operation

📖 Scenario: You are working with a phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to find if a particular phone number exists in the phone book.

🎯 Goal: Build a simple BST and write code to search for a given phone number in it.

📋 What You'll Learn

Create a BST node structure with integer phone numbers

Manually create a BST with given phone numbers

Write a function to search for a phone number in the BST

Print whether the phone number is found or not

💡 Why This Matters

🌍 Real World

BSTs are used in phone books, contact lists, and databases to quickly find information by key.

💼 Career

Understanding BST search is fundamental for software engineers working with data storage, retrieval, and optimization.

1

Create BST Node Structure and Root Node

Create a struct called Node with an int data, and two pointers left and right of type Node*. Then create a Node* variable called root and initialize it with a new node containing the value 50.

DSA C++

// Define struct Node and create root node with value 50
// Your code here

Hint

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

2

Add Left and Right Child Nodes to Root

Add two child nodes to root: set root->left to a new node with value 30 and root->right to a new node with value 70. Both children should have their left and right pointers set to nullptr.

DSA C++

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

Node* root = new Node{50, nullptr, nullptr};
// Add left child with value 30 and right child with value 70 to root
// Your code here

Hint

Attach smaller number to the left and bigger number to the right of root.

3

Write a Function to Search for a Value in BST

Write a function called searchBST that takes a Node* called root and an int key. It should return true if key is found in the BST, otherwise false. Use the BST property to decide whether to search left or right.

DSA C++

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

Node* root = new Node{50, nullptr, nullptr};
root->left = new Node{30, nullptr, nullptr};
root->right = new Node{70, nullptr, nullptr};

// Write searchBST function below
// Your code here

Hint

Check if current node is null or matches key. If not, go left if key is smaller, else right.

4

Search for a Phone Number and Print Result

Call searchBST with root and the key 70. Print "Found" if the function returns true, otherwise print "Not Found".

DSA C++

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

Node* root = new Node{50, nullptr, nullptr};
root->left = new Node{30, nullptr, nullptr};
root->right = new Node{70, nullptr, nullptr};

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

// Call searchBST with key 70 and print "Found" or "Not Found"
// Your code here

Hint

Use an if statement to print "Found" if searchBST returns true, else "Not Found".