BST Property and Why It Matters in DSA Java - 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 Java

if (node.left != null && node.left.value [1] node.value) {
    // valid left child
}

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.

2fill in blank

medium

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

DSA Java

if (node.right != null && node.right.value [1] node.value) {
    // valid right child
}

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.

3fill in blank

hard

Fix the error in the BST validation condition for the left subtree.

DSA Java

return (node.left == null || node.left.value [1] node.value) && isValidBST(node.left) && isValidBST(node.right);

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 and break strict BST rules.

Using '>' which reverses the condition.

The left subtree values must be strictly less than the node's value to maintain BST property.

4fill in blank

hard

Fill both blanks to complete the BST validation for left and right children.

DSA Java

return (node.left == null || node.left.value [1] node.value) && (node.right == null || node.right.value [2] node.value);

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

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using non-strict comparisons like '<=' or '>=' which allow duplicates.

Swapping the operators for left and right children.

Left child values must be less than node's value, right child values must be greater.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps node values to their left or right child check.

DSA Java

Map<Integer, Boolean> check = Map.of(
    [1], node.left != null && node.left.value [2] node.value,
    [3], node.right != null && node.right.value [2] node.value
);

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

Anode.left.value

B<

Cnode.right.value

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same key for both map entries.

Using wrong comparison operators for left or right child.

Map keys are left and right child values; left child must be less than node, right child greater.

Practice

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

easy

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

B. Each node has exactly two children.

C. All nodes have the same value.

D. Nodes are arranged in a complete binary tree shape.

Solution

1. Step 1: Understand BST definition

   A BST is defined by the order of values: left subtree nodes are smaller, 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 incorrect 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 A

4. Quick Check:

   BST property = For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. [OK]

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

Common Mistakes:

• Thinking BST requires exactly two children per node
• Confusing BST with balanced or complete trees
• Assuming all nodes have the same value

2. Which of the following Java method signatures correctly checks if a tree node satisfies the BST property for its immediate children?

easy

A. boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; }

B. boolean isBSTNode(TreeNode node) { return node.left.val > node.val && node.right.val < node.val; }

C. boolean isBSTNode(TreeNode node) { return node.left.val <= node.val && node.right.val >= node.val; }

D. boolean isBSTNode(TreeNode node) { return node.left == null && node.right == null; }

Solution

1. Step 1: Recall BST node condition

   For a node, left child's value must be less than node's value, right child's value must be greater.

2. Step 2: Analyze method signatures

   boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } correctly checks left.val < node.val and right.val > node.val. Others reverse or relax conditions or check leaf status.

3. Final Answer:

   boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } -> Option A

4. Quick Check:

   Left < node < Right condition = boolean isBSTNode(TreeNode node) { return node.left.val < node.val && node.right.val > node.val; } [OK]

Hint: Check left < node < right for BST node [OK]

Common Mistakes:

• Using <= or >= instead of < and >
• Swapping left and right comparisons
• Checking if node is leaf instead of BST property

3. Consider the following Java code snippet that inserts values into a BST. What will be the in-order traversal output after inserting 10, 5, 15, 3, 7?

medium

A. 10 -> 5 -> 3 -> 7 -> 15 -> null

B. 15 -> 10 -> 7 -> 5 -> 3 -> null

C. 3 -> 5 -> 7 -> 10 -> 15 -> null

D. 5 -> 3 -> 7 -> 10 -> 15 -> null

Solution

1. Step 1: Insert nodes into BST

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

2. Step 2: Perform in-order traversal

   In-order visits left subtree, node, right subtree: 3, 5, 7, 10, 15.

3. Final Answer:

   3 -> 5 -> 7 -> 10 -> 15 -> null -> Option C

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

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

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Inserting nodes incorrectly violating BST property
• Forgetting to include all nodes in traversal

4. Given this Java method to check if a tree is a BST, what is the bug?

boolean isBST(TreeNode node, int min, int max) {
  if (node == null) return true;
  if (node.val <= min || node.val >= max) return false;
  return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
}

medium

A. The method should use < and > instead of <= and >= for comparisons.

B. The base case should return false when node is null.

C. The method does not check the entire subtree values properly.

D. The initial call must provide correct min and max values.

Solution

1. Step 1: Understand method logic

   The method uses min and max bounds to check BST property recursively.

2. Step 2: Identify bug

   The method logic is correct, but if initial min and max are not set properly (e.g., Integer.MIN_VALUE and Integer.MAX_VALUE), it may fail.

3. Final Answer:

   The initial call must provide correct min and max values. -> Option D

4. Quick Check:

   Proper initial bounds needed = The initial call must provide correct min and max values. [OK]

Hint: Always start with full integer range for min and max [OK]

Common Mistakes:

• Changing base case to false on null node
• Misusing <= and >= causing off-by-one errors
• Ignoring initial min/max parameters in first call

5. You have a BST where duplicate values are allowed only on the right subtree. Which modification to the BST property is correct to maintain this rule?

hard

A. Left subtree nodes <= node.val, right subtree nodes > node.val

B. Left subtree nodes < node.val, right subtree nodes >= node.val

C. Left subtree nodes <= node.val, right subtree nodes >= node.val

D. Left subtree nodes < node.val, right subtree nodes > node.val

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates allowed only on right subtree means right subtree can have values equal or greater than node.

2. Step 2: Adjust BST property accordingly

   Left subtree must have strictly smaller values, right subtree must have values greater or equal to node.

3. Final Answer:

   Left subtree nodes < node.val, right subtree nodes >= node.val -> Option B

4. Quick Check:

   Duplicates on right = left < node, right >= node [OK]

Hint: Allow equals only on right side with >= [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= on left subtree allowing duplicates there
• Forgetting strict less than on left subtree