BST Property and Why It Matters in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a BST

What is the output of the inorder traversal of this BST after inserting the values 10, 5, 15, 3, 7, 12, 18 in that order?

DSA C++

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

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

void inorder(Node* root, std::vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

int main() {
    Node* root = nullptr;
    int values[] = {10, 5, 15, 3, 7, 12, 18};
    for (int v : values) root = insert(root, v);
    std::vector<int> result;
    inorder(root, result);
    for (int x : result) std::cout << x << " ";
    return 0;
}

A [5, 3, 7, 10, 15, 12, 18]

B [10, 5, 3, 7, 15, 12, 18]

C [3, 5, 7, 10, 12, 15, 18]

D [18, 15, 12, 10, 7, 5, 3]

💡 Hint

Inorder traversal of a BST always gives sorted values.

Inorder traversal visits nodes in ascending order for a BST. The inserted values create a BST where inorder traversal outputs the sorted list.

🧠 Conceptual

intermediate

Why BST Property is Important for Search Efficiency

Why does the BST property help in efficient searching compared to an unsorted binary tree?

A Because it balances the tree automatically without extra operations.

B Because it allows skipping half of the tree at each step by comparing values.

C Because it stores all values in a linked list inside each node.

D Because it stores values in random order to confuse the search.

💡 Hint

Think about how comparing values guides the search direction.

The BST property ensures left children are smaller and right children are larger, so at each node you can decide which subtree to search, effectively halving the search space.

🔧 Debug

advanced

Identify the Bug in BST Insertion

What error will this BST insertion code cause when inserting duplicate values?

DSA C++

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

A Duplicates are inserted to the right subtree always.

B Duplicates cause infinite recursion leading to stack overflow.

C Duplicates are inserted to the left subtree always.

D Duplicates are ignored; no insertion happens for equal values.

💡 Hint

Check what happens when val == root->val.

The code does not handle the case when val equals root->val, so it returns root without inserting duplicates.

❓ Predict Output

advanced

Output After Deleting a Node with Two Children in BST

Given the BST constructed by inserting 20, 10, 30, 5, 15, 25, 35, what is the inorder traversal output after deleting node 20?

DSA C++

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

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

Node* findMin(Node* root) {
    while (root && root->left) root = root->left;
    return root;
}

Node* deleteNode(Node* root, int val) {
    if (!root) return nullptr;
    if (val < root->val) root->left = deleteNode(root->left, val);
    else if (val > root->val) root->right = deleteNode(root->right, val);
    else {
        if (!root->left) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

void inorder(Node* root, std::vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

int main() {
    Node* root = nullptr;
    int values[] = {20, 10, 30, 5, 15, 25, 35};
    for (int v : values) root = insert(root, v);
    root = deleteNode(root, 20);
    std::vector<int> result;
    inorder(root, result);
    for (int x : result) std::cout << x << " ";
    return 0;
}

A [5, 10, 15, 25, 30, 35]

B [5, 10, 15, 20, 25, 30, 35]

C [5, 10, 15, 25, 20, 30, 35]

D [10, 15, 25, 30, 35]

💡 Hint

Deleting a node with two children replaces it with the smallest node in the right subtree.

Node 20 is replaced by 25 (minimum in right subtree). Then 25 is deleted from its original position. The inorder traversal reflects this change.

🧠 Conceptual

expert

Effect of Violating BST Property on Search

If a binary tree does not maintain the BST property, what is the worst-case time complexity of searching for a value compared to a BST?

A It becomes O(n) because the tree may behave like a linked list.

B It remains O(log n) because the tree structure is unchanged.

C It improves to O(1) because values are randomly distributed.

D It becomes O(n log n) due to extra comparisons.

💡 Hint

Without BST property, you cannot decide which subtree to skip.

Without the BST property, searching may require visiting every node, leading to linear time complexity.