BST Search Operation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Search for Existing Value

What is the output of the following C++ code that searches for the value 15 in a BST?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Node* search(Node* root, int val) {
    if (!root || root->data == val) return root;
    if (val < root->data) return search(root->left, val);
    return search(root->right, val);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    Node* result = search(root, 15);
    if (result) std::cout << result->data << std::endl;
    else std::cout << "Not found" << std::endl;
    return 0;
}

A 7

B Not found

C 10

D 15

💡 Hint

Think about how the search function returns the node if found.

The search function returns the node with data 15 because it exists in the BST. The output prints the data of the found node.

❓ Predict Output

intermediate

Output of BST Search for Non-Existing Value

What is the output of the following C++ code that searches for the value 8 in a BST?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

Node* search(Node* root, int val) {
    if (!root || root->data == val) return root;
    if (val < root->data) return search(root->left, val);
    return search(root->right, val);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    Node* result = search(root, 8);
    if (result) std::cout << result->data << std::endl;
    else std::cout << "Not found" << std::endl;
    return 0;
}

A 7

B Not found

C 8

D 3

💡 Hint

Check if the value 8 exists in the BST nodes.

The value 8 is not inserted in the BST, so the search returns nullptr and prints 'Not found'.

🧠 Conceptual

advanced

Time Complexity of BST Search

What is the worst-case time complexity of searching for a value in a Binary Search Tree (BST) with n nodes?

A O(n)

B O(log n)

C O(n log n)

D O(1)

💡 Hint

Consider the shape of the BST in the worst case.

In the worst case, the BST is skewed (like a linked list), so search takes O(n) time.

🔧 Debug

advanced

Identify the Bug in BST Search Function

What error will occur when running this BST search function if the value is not found?

DSA C++

Node* search(Node* root, int val) {
    if (root == nullptr) return nullptr;
    if (root->data == val) return root;
    if (val < root->data) return search(root->left, val);
    return search(root->right, val);
}

A Segmentation fault (accessing null pointer)

B Returns nullptr correctly

C Compilation error due to missing return

D Infinite recursion

💡 Hint

What happens if root is nullptr?

The function does not check if root is nullptr before accessing root->data, causing a segmentation fault if value is not found.

🚀 Application

expert

Number of Nodes Visited During BST Search

Given a BST with nodes inserted in this order: 20, 10, 30, 5, 15, 25, 35. How many nodes are visited when searching for the value 25?

A 4

B 2

C 3

D 5

💡 Hint

Count nodes visited from root to the target node.

Search path: 20 -> 30 -> 25. Three nodes visited.