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.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

B. Each node has exactly two children.

C. All nodes have the same value.

D. Nodes are arranged in a complete binary tree structure.

Solution

1. Step 1: Understand BST definition

   A BST requires that for every node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare options with BST property

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches the BST property exactly, while others describe different tree types or incorrect properties.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option A

4. Quick Check:

   BST property = For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. [OK]

Hint: Remember: left < node < right in BST [OK]

Common Mistakes:

• Thinking BST means every node has two children
• Confusing BST with balanced or complete trees
• Assuming all nodes have the same value

2. Which of the following is the correct C++ syntax to declare a node structure for a BST?

easy

A. class Node { int data; Node left; Node right; };

B. struct Node { int data; Node left; Node right; };

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

D. class Node { int data; Node* left; Node* right; };

Solution

1. Step 1: Check pointer usage in node declaration

   BST nodes must use pointers for left and right children to allow dynamic linking.

2. Step 2: Compare struct and class syntax

   struct Node { int data; Node* left; Node* right; }; correctly uses struct with pointers. class Node { int data; Node* left; Node* right; }; uses class but misses access specifiers (defaults private). Declarations using objects instead of pointers for children are incorrect.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option C

4. Quick Check:

   Use pointers for children in BST node [OK]

Hint: Use pointers for child nodes in BST struct [OK]

Common Mistakes:

• Using objects instead of pointers for children
• Forgetting semicolon after struct
• Using class without public access for members

3. Consider the following BST insertion code snippet in C++:

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

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

int main() {
  Node* root = nullptr;
  root = insert(root, 10);
  root = insert(root, 5);
  root = insert(root, 15);
  root = insert(root, 12);
  root = insert(root, 18);
  return 0;
}

What is the in-order traversal output of the BST after these insertions?

medium

A. [10, 12, 5, 15, 18]

B. [10, 5, 15, 12, 18]

C. [18, 15, 12, 10, 5]

D. [5, 10, 12, 15, 18]

Solution

1. Step 1: Understand insertion order and BST structure

   Inserted values: 10 (root), 5 (left), 15 (right), 12 (left of 15), 18 (right of 15).

2. Step 2: Perform in-order traversal (left, root, right)

   Traverse left subtree: 5, root: 10, left of right subtree: 12, root of right subtree: 15, right of right subtree: 18. So output is [5, 10, 12, 15, 18].

3. Final Answer:

   [5, 10, 12, 15, 18] -> Option D

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Ignoring BST insertion rules
• Mixing up left and right subtree traversal

4. The following code attempts to insert a value into a BST but has a bug:

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

What is the main issue with this code regarding BST property?

medium

A. It does not allocate memory for new nodes.

B. Using <= allows duplicate values on the left, which may violate strict BST property.

C. It uses recursion incorrectly causing infinite loops.

D. It does not handle the case when root is null.

Solution

1. Step 1: Analyze the condition for left subtree insertion

   The code uses val <= root->data to decide left subtree insertion, allowing duplicates on the left.

2. Step 2: Understand BST strict property

   Strict BST property requires all left subtree values to be strictly less than the node's value. Allowing duplicates on left can break this.

3. Final Answer:

   Using <= allows duplicate values on the left, which may violate strict BST property. -> Option B

4. Quick Check:

   Strict BST: left < node < right [OK]

Hint: Use < for left subtree to avoid duplicates breaking BST [OK]

Common Mistakes:

• Ignoring duplicate handling in BST
• Thinking recursion causes infinite loops here
• Assuming null root case is missing

5. You have a BST where each node stores an integer. You want to find the kth smallest element efficiently. Which approach best uses the BST property to solve this?

hard

A. Perform an in-order traversal and stop when the kth element is reached.

B. Perform a level-order traversal and count nodes until kth is found.

C. Traverse only the right subtree k times to find the kth smallest.

D. Use pre-order traversal and store all nodes in a list, then sort it.

Solution

1. Step 1: Recall BST in-order traversal property

   In-order traversal visits nodes in ascending order for BST.

2. Step 2: Use in-order traversal to find kth smallest

   By traversing in-order and counting nodes, we can stop at kth node, efficiently finding kth smallest.

3. Final Answer:

   Perform an in-order traversal and stop when the kth element is reached. -> Option A

4. Quick Check:

   In-order traversal = sorted order [OK]

Hint: In-order traversal visits nodes in ascending order [OK]

Common Mistakes:

• Using level-order which is not sorted
• Traversing only right subtree misses smaller values
• Sorting after pre-order wastes time