BST property and invariant in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the sentence to describe the BST property: In a Binary Search Tree, the left subtree of a node contains only nodes with keys {{BLANK_1}} the node's key.

Data Structures Theory

In a Binary Search Tree, the left subtree of a node contains only nodes with keys [1] the node's key.

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

Agreater than

Bunrelated to

Cequal to

Dless than

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing left subtree keys as greater than the node's key.

Thinking keys can be equal in the left subtree.

The BST property states that all keys in the left subtree are less than the node's key.

2fill in blank

medium

Complete the sentence to describe the BST property: The right subtree of a node contains only nodes with keys {{BLANK_1}} the node's key.

Data Structures Theory

The right subtree of a node contains only nodes with keys [1] the node's key.

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

Agreater than

Bunrelated to

Cequal to

Dless than

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming right subtree keys are less than the node's key.

Allowing equal keys in the right subtree.

According to the BST property, all keys in the right subtree are greater than the node's key.

3fill in blank

hard

Fix the error in this BST invariant statement: "For every node, all keys in the left subtree are {{BLANK_1}} or equal to the node's key."

Data Structures Theory

For every node, all keys in the left subtree are [1] or equal to the node's key.

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

Agreater than

Bless than

Cgreater than or equal to

Dless than or equal to

Attempts:

3 left

💡 Hint

Common Mistakes

Allowing equal keys in the left subtree.

Confusing less than with greater than.

The BST property requires keys in the left subtree to be strictly less than the node's key, not equal or greater.

4fill in blank

hard

Fill both blanks to complete the BST invariant: "For every node, all keys in the left subtree are {{BLANK_1}} the node's key, and all keys in the right subtree are {{BLANK_2}} the node's key."

Data Structures Theory

For every node, all keys in the left subtree are [1] the node's key, and all keys in the right subtree are [2] the node's key.

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

Aless than

Bequal to

Cgreater than

Dunrelated to

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up left and right subtree key comparisons.

Allowing equal keys on either side.

The BST property requires left subtree keys to be less than and right subtree keys to be greater than the node's key.

5fill in blank

hard

Fill all three blanks to complete the BST property check code snippet: "if node is not None: if node.left is not None and node.left.key {{BLANK_1}} node.key: raise ValueError('BST property violated'); if node.right is not None and node.right.key {{BLANK_2}} node.key: raise ValueError('BST property violated'); check(node.left); check(node.right)"

Data Structures Theory

if node is not None:
    if node.left is not None and node.left.key [1] node.key:
        raise ValueError('BST property violated')
    if node.right is not None and node.right.key [2] node.key:
        raise ValueError('BST property violated')
    check(node.left)
    check(node.right)

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

A>=

B<=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators that do not detect violations.

Confusing which side uses which comparison.

The left child's key must be less than the node's key (violation if left.key >= node.key). The right child's key must be greater than the node's key (violation if right.key <= node.key). The code raises an error if these conditions are violated.