BST property and invariant in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the BST Property

Which of the following best describes the Binary Search Tree (BST) property?

A For every node, the values in the left subtree are equal to the node's value, and the right subtree contains greater values.

B For every node, all values in its left subtree are greater than the node's value, and all values in its right subtree are less.

C For every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

D For every node, the left and right subtrees contain equal numbers of nodes.

💡 Hint

Think about how the tree helps you find values quickly by comparing with the current node.

The BST property ensures that for each node, all values in the left subtree are smaller, and all values in the right subtree are larger. This allows efficient searching.

📋 Factual

intermediate

Invariant Maintenance in BST Operations

Which invariant must be maintained after inserting a new value into a BST?

A The tree remains balanced with equal height on both sides.

B The BST property that left subtree values are less and right subtree values are greater than the node's value.

C All leaf nodes must be at the same depth.

D The root node must always have the smallest value.

💡 Hint

Focus on what property defines a BST regardless of shape.

After insertion, the BST property must hold so that searching remains efficient. Balancing or leaf depth equality is not guaranteed in a basic BST.

🔍 Analysis

advanced

Detecting BST Property Violation

Given the following tree structure, which node violates the BST property?

      10
     /  \
    5    15
   / \     \
  2   12    20

A Node with value 12

B Node with value 5

C Node with value 15

D Node with value 20

💡 Hint

Check if all nodes in the left subtree are less than 10 and all in the right subtree are greater than 10.

The node with value 12 is in the left subtree of 10 but is greater than 10, violating the BST property.

❓ Comparison

advanced

Comparing BST and Binary Tree Properties

Which statement correctly distinguishes a Binary Search Tree (BST) from a general Binary Tree?

A A BST requires the left child to be smaller and the right child to be larger than the node, while a Binary Tree has no such ordering requirement.

B A BST requires nodes to have at most two children, while a Binary Tree can have any number of children.

C A BST must be a complete tree, while a Binary Tree can be incomplete.

D A BST stores only unique values, while a Binary Tree allows duplicates.

💡 Hint

Think about the ordering rules that make searching efficient.

A BST has a strict ordering rule for left and right children, unlike a general Binary Tree which has no ordering constraints.

❓ Reasoning

expert

Effect of Violating BST Invariant on Search

If a node in a BST violates the BST property, what is the most likely consequence when searching for a value?

A The search will convert the tree into a balanced BST automatically.

B The search will ignore the violation and continue correctly.

C The search will always find the value faster than in a balanced BST.

D The search might fail to find the value even if it exists in the tree.

💡 Hint

Consider how the search algorithm relies on the BST property to decide which subtree to explore.

If the BST property is violated, the search may go down the wrong path and miss the target value even if it is present.

Practice

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

easy

A. All nodes have exactly two children.

B. Nodes are arranged in a circular linked list.

C. Left child nodes are smaller, right child nodes are larger than the parent node.

D. Each node stores a unique key with no order.

Solution

1. Step 1: Understand BST node arrangement

   A BST arranges nodes so that left children have smaller values and right children have larger values than their parent node.

2. Step 2: Compare options with BST definition

   Left child nodes are smaller, right child nodes are larger than the parent node. correctly states this property. Other options describe different or incorrect structures.

3. Final Answer:

   Left child nodes are smaller, right child nodes are larger than the parent node. -> Option C

4. Quick Check:

   BST property = left < parent < right [OK]

Hint: Remember BST means left smaller, right larger [OK]

Common Mistakes:

• Thinking all nodes must have two children
• Confusing BST with other tree types
• Ignoring the order property in BST

2. Which of the following is the correct way to check if a node's left child maintains the BST property?

easy

A. left_child.value > node.value

B. left_child.value < node.value

C. left_child.value == node.value

D. left_child.value >= node.value

Solution

1. Step 1: Recall BST left child rule

   In a BST, the left child's value must be less than the parent's value.

2. Step 2: Match this rule to options

   left_child.value < node.value correctly states left_child.value < node.value. Other options violate this rule.

3. Final Answer:

   left_child.value < node.value -> Option B

4. Quick Check:

   Left child < parent [OK]

Hint: Left child must be smaller than parent [OK]

Common Mistakes:

• Using greater than or equal instead of less than
• Allowing equal values on left child
• Confusing left and right child rules

3. Given the BST below, what is the correct in-order traversal output?

      10
     /  \
    5    15
   / \     \
  3   7     20

medium

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

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

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

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

Solution

1. Step 1: Understand in-order traversal

   In-order traversal visits left subtree, then node, then right subtree, producing sorted order in BST.

2. Step 2: Traverse the tree in-order

   Left subtree of 10: nodes 3, 5, 7 in order; then 10; then right subtree 15, 20.

3. Final Answer:

   [3, 5, 7, 10, 15, 20] -> Option A

4. Quick Check:

   In-order traversal = sorted nodes [OK]

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

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Listing nodes in insertion order
• Reversing the traversal order

4. Consider the following BST insertion code snippet. What is the error?

def insert(node, value):
    if node is null:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

medium

A. The code does not handle duplicate values correctly.

B. The base case for node is incorrect.

C. The recursive calls do not update the tree.

D. The function does not return the updated node.

Solution

1. Step 1: Analyze duplicate handling in insertion

   The code inserts duplicates into the right subtree without restriction, which may violate BST uniqueness if duplicates are not allowed.

2. Step 2: Check other parts of the code

   Base case and recursive updates are correct; function returns updated node properly.

3. Final Answer:

   The code does not handle duplicate values correctly. -> Option A

4. Quick Check:

   Duplicates need special handling in BST insert [OK]

Hint: Check how duplicates are treated in insertion [OK]

Common Mistakes:

• Assuming duplicates are automatically handled
• Ignoring return statements in recursion
• Confusing base case with recursive case

5. You want to verify if a binary tree is a valid BST. Which approach correctly checks the BST property for all nodes?

hard

A. Check if the tree has unique values only.

B. Check if the tree is balanced and has no cycles.

C. Check if each node's left child is smaller and right child is larger, recursively.

D. Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits.

Solution

1. Step 1: Understand BST validation requirements

   Each node must satisfy that all nodes in its left subtree are smaller and all in right subtree are larger, not just immediate children.

2. Step 2: Evaluate approaches

   Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits. uses min and max limits to ensure all descendants satisfy BST property, which is correct. Check if each node's left child is smaller and right child is larger, recursively. only checks immediate children, which is insufficient.

3. Final Answer:

   Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits. -> Option D

4. Quick Check:

   BST validation requires range checks, not just immediate children [OK]

Hint: Use min/max limits to validate BST recursively [OK]

Common Mistakes:

• Checking only immediate children values
• Confusing BST property with tree balance
• Assuming unique values guarantee BST