BST Property and Why It Matters in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a BST

What is the output of the inorder traversal of this BST?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BST {
    public static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        inorder(root);
    }
}

A 10 5 3 7 15

B 3 5 7 10 15

C 15 10 7 5 3

D 5 3 7 10 15

💡 Hint

Inorder traversal of a BST prints values in sorted order.

Inorder traversal visits left subtree, then root, then right subtree. For BST, this results in sorted order.

🧠 Conceptual

intermediate

Why Does BST Property Matter for Search?

Why is the BST property important for efficient search operations?

A It allows skipping half of the tree at each step, reducing search time to O(log n) on average.

B It stores all values in a linked list for quick sequential access.

C It guarantees all nodes have two children, making the tree balanced.

D It sorts the nodes by insertion order to speed up search.

💡 Hint

Think about how the BST property helps decide which subtree to search next.

The BST property lets us decide to go left or right based on comparison, skipping half the nodes each time on average.

🔧 Debug

advanced

Identify the Bug Breaking BST Property

Which option shows code that breaks the BST property when inserting a node?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BST {
    public static Node insert(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insert(root.left, val);
        else root.right = insert(root.right, val);
        return root;
    }
}

A if (val <= root.val) root.left = insert(root.left, val); else root.right = insert(root.right, val);

B if (val < root.val) root.left = insert(root.left, val); else root.right = insert(root.right, val);

C if (val < root.val) root.right = insert(root.right, val); else root.left = insert(root.left, val);

D if (val > root.val) root.left = insert(root.left, val); else root.right = insert(root.right, val);

💡 Hint

Check which side the smaller values are inserted.

Option C inserts smaller values to the right subtree, breaking BST property.

❓ Predict Output

advanced

Result of Deleting a Node in BST

What is the inorder traversal output after deleting node 5 from this BST?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class BST {
    public static Node delete(Node root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = delete(root.left, key);
        else if (key > root.val) root.right = delete(root.right, key);
        else {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            root.val = minValue(root.right);
            root.right = delete(root.right, root.val);
        }
        return root;
    }

    public static int minValue(Node root) {
        int minv = root.val;
        while (root.left != null) {
            root = root.left;
            minv = root.val;
        }
        return minv;
    }

    public static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        root = delete(root, 5);
        inorder(root);
    }
}

A 3 7 10 15

B 3 5 7 10 15

C 7 10 15

D 3 10 15

💡 Hint

Deleting node with two children replaces it with smallest value in right subtree.

Node 5 is replaced by 7 (min in right subtree), then 7 is deleted from original position.

🧠 Conceptual

expert

Why Can BST Become Inefficient Without Balancing?

Why can a BST become inefficient if it is not balanced?

A Because it uses too much memory when balanced.

B Because unbalanced BSTs cannot store duplicate values.

C Because balancing causes nodes to lose their values.

D Because it can degrade into a linked list, making search O(n) instead of O(log n).

💡 Hint

Think about the shape of the tree and how it affects search steps.

If BST is skewed, it behaves like a linked list, losing the efficiency of binary search.

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