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 in that order?

DSA C

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

// Assume insert function inserts nodes maintaining BST property
// Inorder traversal prints nodes in sorted order

// Insert sequence: 10, 5, 15, 3, 7
// Then perform inorder traversal and print values separated by spaces.

A 3 5 7 10 15

B 10 5 3 7 15

C 15 10 7 5 3

D 5 3 7 10 15

💡 Hint

Inorder traversal of a BST prints values in ascending order.

Inorder traversal visits left subtree, then node, then right subtree. For BST, this results in sorted order of values.

🧠 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 after every insertion.

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

C Because it stores duplicate values in the right subtree only.

D Because it allows skipping half of the tree at each step, similar to binary search.

💡 Hint

Think about how the BST property orders values relative to each node.

The BST property ensures left subtree has smaller values and right subtree has larger values, allowing search to discard half the tree at each step.

🔧 Debug

advanced

Identify the Error in BST Insertion Code

What error will this BST insertion code cause when inserting a value equal to a node's data?

DSA C

struct Node* insert(struct Node* root, int val) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }
    // No else case for val == root->data
    return root;
}

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

B Infinite recursion occurs causing stack overflow.

C The code inserts duplicates always to the left subtree.

D The code inserts duplicates always to the right subtree.

💡 Hint

Check what happens when val equals root->data.

Since no else case handles val == root->data, the function returns root without inserting duplicates, effectively ignoring them.

❓ Predict Output

advanced

Output After Deleting a Node with Two Children in BST

Given a BST with nodes 20, 10, 30, 5, 15, 25, 35, what is the inorder traversal output after deleting node 20?

DSA C

// BST nodes inserted in order: 20,10,30,5,15,25,35
// Delete node with value 20 (which has two children)
// Then perform inorder traversal and print values separated by spaces.

A 5 10 15 20 25 30 35

B 5 10 15 25 30 35

C 5 10 15 25 20 30 35

D 10 15 25 30 35

💡 Hint

When deleting a node with two children, replace it with its inorder successor.

Node 20 is replaced by its inorder successor 25, then 25 is deleted from right subtree. Inorder traversal reflects updated tree.

🧠 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 improves to O(1) because nodes are randomly placed.

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

C It becomes O(n) because the tree behaves like an unsorted list.

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

💡 Hint

Without BST property, you cannot skip half the nodes during search.

Without BST property, search may need to check every node, resulting in linear time O(n).

Practice

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

easy

A. All leaf nodes are at the same depth.

B. Each node has exactly two children.

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

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

Solution

1. Step 1: Understand BST definition

   A BST is defined by the order property where left subtree nodes are smaller and right subtree nodes are larger than the current node.

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. Other options describe different tree types or 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 D

4. Quick Check:

   BST property = left < node < right [OK]

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

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which of the following is the correct syntax to check if a node's left child value is less than the node's value in C?

easy

A. if (node->left->value < node->value) {}

B. if (node.left.value < node.value) {}

C. if (node->left.value < node->value) {}

D. if (node.left->value < node.value) {}

Solution

1. Step 1: Understand C struct pointer access

   In C, to access a member of a struct pointer, use '->'. So node->left accesses left child pointer.

2. Step 2: Check each option for correct pointer syntax

   if (node->left->value < node->value) {} uses node->left->value correctly. Others mix '.' and '->' incorrectly.

3. Final Answer:

   if (node->left->value < node->value) {} -> Option A

4. Quick Check:

   Use '->' for pointer members in C [OK]

Hint: Use '->' to access struct pointer members in C [OK]

Common Mistakes:

• Using '.' instead of '->' for pointers
• Mixing '.' and '->' incorrectly
• Forgetting to check if left child is NULL before access

3. Given the following BST insertion code snippet in C, what will be the inorder traversal output after inserting values 10, 5, 15, 3, 7?

medium

A. [15, 10, 7, 5, 3]

B. [10, 5, 15, 3, 7]

C. [3, 5, 7, 10, 15]

D. [5, 3, 7, 10, 15]

Solution

1. Step 1: Insert values into BST following property

   Insert 10 as root, 5 left of 10, 15 right of 10, 3 left of 5, 7 right of 5.

2. Step 2: Perform inorder traversal (left, node, right)

   Inorder visits nodes in ascending order: 3, 5, 7, 10, 15.

3. Final Answer:

   [3, 5, 7, 10, 15] -> Option C

4. Quick Check:

   Inorder traversal of BST = sorted values [OK]

Hint: Inorder traversal of BST gives sorted order [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Inserting nodes incorrectly violating BST property
• Reading traversal output in insertion order

4. Consider this C code snippet for BST insertion. What is the error?

void insert(Node** root, int val) {
  if (*root == NULL) {
    *root = malloc(sizeof(Node));
    (*root)->value = val;
    (*root)->left = NULL;
    (*root)->right = NULL;
  } else if (val < (*root)->value) {
    insert(&(*root)->left, val);
  } else {
    insert(&(*root)->right, val);
  }
}

medium

A. Missing check for duplicate values before insertion.

B. No error; code correctly inserts into BST.

C. Incorrect use of pointer to pointer for root parameter.

D. Memory allocation size should be sizeof(Node*), not sizeof(Node).

Solution

1. Step 1: Analyze insertion logic for duplicates

   The code inserts values less than current node to left, else to right, so duplicates go right without check.

2. Step 2: Identify missing duplicate check

   BST usually avoids duplicates or handles them explicitly; this code lacks that check.

3. Final Answer:

   Missing check for duplicate values before insertion. -> Option A

4. Quick Check:

   Duplicates need explicit handling in BST insert [OK]

Hint: Check for duplicates before inserting in BST [OK]

Common Mistakes:

• Assuming duplicates are allowed without check
• Confusing pointer usage in recursive calls
• Incorrect malloc size for struct allocation

5. You have a BST where the property is violated at one node: the right child has a smaller value than the parent. How does this violation affect searching for a value larger than the parent in the BST?

hard

A. Search will always return the parent node regardless of the value.

B. Search may fail or return incorrect results because the BST property is broken.

C. Search will be faster because smaller values on right reduce search space.

D. Search will still work correctly because only one node is wrong.

Solution

1. Step 1: Understand BST property importance in search

   BST search relies on left < node < right property to decide which subtree to explore.

2. Step 2: Analyze effect of violation on search

   If right child is smaller, search for larger values may wrongly go left or miss nodes, causing failure or wrong results.

3. Final Answer:

   Search may fail or return incorrect results because the BST property is broken. -> Option B

4. Quick Check:

   BST property violation breaks search correctness [OK]

Hint: BST property must hold for correct search [OK]

Common Mistakes:

• Assuming one violation doesn't affect search
• Thinking search speed improves with violation
• Believing search always returns parent node