BST Property and Why It Matters in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a node's left child value is less than the node's value.

DSA C

if (node->left != NULL && node->left->value [1] node->value) {
    // left child is less
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' for left child comparison.

Using '==' which only checks equality, not order.

In a BST, the left child's value must be less than the node's value, so '<' is correct.

2fill in blank

medium

Complete the code to check if a node's right child value is greater than the node's value.

DSA C

if (node->right != NULL && node->right->value [1] node->value) {
    // right child is greater
}

Drag options to blanks, or click blank then click option'

A>

B<

C<=

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for right child comparison.

Using '==' which only checks equality, not order.

In a BST, the right child's value must be greater than the node's value, so '>' is correct.

3fill in blank

hard

Fix the error in the code that checks BST property for the left child.

DSA C

if (node->left != NULL && node->left->value [1] node->value) {
    // correct BST property
}

Drag options to blanks, or click blank then click option'

A==

B<=

C>=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' which allows equal or greater values on left child.

Using '<=' which allows equal values, violating strict BST property.

The left child's value must be strictly less than the node's value, so '<' is correct.

4fill in blank

hard

Fill both blanks to complete the BST validation condition for a node.

DSA C

if ((node->left == NULL || node->left->value [1] node->value) && (node->right == NULL || node->right->value [2] node->value)) {
    // node satisfies BST property
}

Drag options to blanks, or click blank then click option'

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' or '>=' which allow equal values, violating strict BST rules.

Swapping operators between left and right child checks.

Left child must be less than node ('<'), right child must be greater than node ('>').

5fill in blank

hard

Fill all three blanks to complete the recursive BST validation function.

DSA C

int isBST(Node* node) {
    if (node == NULL) return 1;
    if ((node->left == NULL || node->left->value [1] node->value) &&
        (node->right == NULL || node->right->value [2] node->value) &&
        isBST(node->left) && isBST(node->right)) {
        return [3];
    }
    return 0;
}

Drag options to blanks, or click blank then click option'

A<

B>

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of 1 when BST property holds.

Using wrong comparison operators for left or right child.

Left child must be less than node ('<'), right child greater ('>'), and return 1 for true.

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