BST Property and Why It Matters in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Binary Search Tree (BST) property?

In a BST, for every node, all values in its left subtree are smaller, and all values in its right subtree are larger than the node's value.

beginner

Why does the BST property matter for searching?

Because the BST property keeps values ordered, it allows searching by comparing values and moving left or right, making search faster than checking every node.

beginner

How does the BST property help in insertion?

Insertion uses the BST property to find the correct spot by comparing values and moving left or right until an empty spot is found, keeping the tree ordered.

intermediate

What happens if the BST property is broken?

If the BST property is broken, searching and other operations become inefficient because the tree loses its order, making it like a random tree.

intermediate

How does the BST property affect the time complexity of operations?

The BST property allows operations like search, insert, and delete to run in O(log n) time on average by reducing the search space at each step.

What must be true about all nodes in the left subtree of a BST node?

A They can be any value

B They are larger than the node's value

C They are smaller than the node's value

D They are equal to the node's value

In a BST, all nodes in the left subtree must have values smaller than the node's value.

Why is the BST property important for efficient searching?

A It keeps the tree balanced automatically

B It allows skipping half of the tree at each step

C It stores duplicate values

D It makes the tree a linked list

The BST property lets us decide to go left or right, skipping half the nodes, making search faster.

If a node's right subtree contains a smaller value than the node, what happens?

A The BST property is maintained

B The node is deleted

C The tree becomes balanced

D The BST property is broken

Right subtree nodes must be larger; smaller values there break the BST property.

What is the average time complexity of searching in a BST with the property maintained?

A O(log n)

B O(1)

C O(n)

D O(n log n)

With the BST property, search takes O(log n) time on average by halving the search space each step.

Which operation relies on the BST property to find the correct place to add a new node?

A Insertion

B Traversal

C Deletion

D Balancing

Insertion uses the BST property to find the correct spot by comparing values and moving left or right.

Explain the BST property and why it is important for searching and insertion.

Think about how the tree stays ordered and how that helps find values quickly.

Describe what happens if the BST property is broken and how it affects tree operations.

Consider how the tree's usefulness depends on its order.

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