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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes in a BST

What is the printed state of the BST after inserting the following values in order: 10, 5, 15, 3, 7?

DSA C#

class Node {
    public int Value;
    public Node Left, Right;
    public Node(int value) { Value = value; Left = Right = null; }
}

class BST {
    public Node Root;
    public void Insert(int value) {
        Root = InsertRec(Root, value);
    }
    private Node InsertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.Value) root.Left = InsertRec(root.Left, value);
        else root.Right = InsertRec(root.Right, value);
        return root;
    }
    public void PrintInOrder(Node root) {
        if (root == null) return;
        PrintInOrder(root.Left);
        System.Console.Write(root.Value + " -> ");
        PrintInOrder(root.Right);
    }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Insert(3);
tree.Insert(7);
tree.PrintInOrder(tree.Root);
System.Console.WriteLine("null");

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

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

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

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

💡 Hint

Remember that in-order traversal of a BST prints values in ascending order.

In-order traversal visits left subtree, then node, then right subtree. For a BST, this prints values sorted ascending.

🧠 Conceptual

intermediate

Why BST Property is Important for Search Efficiency

Why does the BST property (left child < node < right child) help in efficient searching?

A It stores all values in a linked list, making search linear.

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

C It sorts values after insertion, so search is always O(n log n).

D It balances the tree automatically, ensuring constant time search.

💡 Hint

Think about how binary search works on sorted data.

The BST property lets us decide to go left or right subtree based on comparison, halving the search space each step.

🔧 Debug

advanced

Identify the Error in BST Insertion Code

What error will this BST insertion code cause when inserting duplicate values? class BST { public Node Root; public void Insert(int value) { Root = InsertRec(Root, value); } private Node InsertRec(Node root, int value) { if (root == null) return new Node(value); if (value < root.Value) root.Left = InsertRec(root.Left, value); else root.Right = InsertRec(root.Right, value); return root; } }

A Duplicates cause a compile-time error.

B Duplicates are ignored and not inserted at all.

C Duplicates will be inserted to the right subtree, possibly unbalancing the tree.

D Duplicates cause a stack overflow due to infinite recursion.

💡 Hint

Check how the code handles values equal to the current node.

The code inserts duplicates to the right subtree, which can cause the tree to become skewed if many duplicates exist.

❓ Predict Output

advanced

Output After Deleting a Node with Two Children in BST

Given this BST and deletion of node 10, what is the in-order traversal output? Insert order: 10, 5, 15, 3, 7, 12, 18 Delete node: 10 Deletion replaces node with its in-order successor.

DSA C#

class Node {
    public int Value;
    public Node Left, Right;
    public Node(int value) { Value = value; Left = Right = null; }
}

class BST {
    public Node Root;
    public void Insert(int value) {
        Root = InsertRec(Root, value);
    }
    private Node InsertRec(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.Value) root.Left = InsertRec(root.Left, value);
        else root.Right = InsertRec(root.Right, value);
        return root;
    }
    public void Delete(int value) {
        Root = DeleteRec(Root, value);
    }
    private Node DeleteRec(Node root, int value) {
        if (root == null) return root;
        if (value < root.Value) root.Left = DeleteRec(root.Left, value);
        else if (value > root.Value) root.Right = DeleteRec(root.Right, value);
        else {
            if (root.Left == null) return root.Right;
            else if (root.Right == null) return root.Left;
            root.Value = MinValue(root.Right);
            root.Right = DeleteRec(root.Right, root.Value);
        }
        return root;
    }
    private int MinValue(Node root) {
        int minv = root.Value;
        while (root.Left != null) {
            root = root.Left;
            minv = root.Value;
        }
        return minv;
    }
    public void PrintInOrder(Node root) {
        if (root == null) return;
        PrintInOrder(root.Left);
        System.Console.Write(root.Value + " -> ");
        PrintInOrder(root.Right);
    }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Insert(3);
tree.Insert(7);
tree.Insert(12);
tree.Insert(18);
tree.Delete(10);
tree.PrintInOrder(tree.Root);
System.Console.WriteLine("null");

A 5 -> 7 -> 12 -> 15 -> 18 -> null

B 3 -> 5 -> 7 -> 10 -> 12 -> 15 -> 18 -> null

C 3 -> 5 -> 7 -> 15 -> 12 -> 18 -> null

D 3 -> 5 -> 7 -> 12 -> 15 -> 18 -> null

💡 Hint

The in-order successor is the smallest value in the right subtree.

Node 10 is replaced by 12 (its in-order successor). The tree then has 12 in place of 10, and 12 is removed from its original position.

🧠 Conceptual

expert

Why BST Can Degenerate and How to Prevent It

Which statement best explains why a BST can become inefficient and how to prevent it?

A If inserted values are sorted, BST becomes a linked list; balancing techniques like AVL or Red-Black trees prevent this.

B BSTs become inefficient only if duplicates are inserted; avoiding duplicates fixes this.

C BSTs always remain balanced regardless of insertion order; no prevention needed.

D BSTs become inefficient if nodes have two children; deleting such nodes prevents inefficiency.

💡 Hint

Think about what happens when inserting sorted data into a BST.

Inserting sorted data creates a skewed tree like a linked list, losing efficiency. Balanced BSTs use rotations to keep height low.

Practice

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

easy

A. Each node has exactly two children.

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

C. All nodes have the same value.

D. Nodes are arranged in a circular linked list.

Solution

1. Step 1: Understand BST node arrangement

   A BST is defined by the rule that for every node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare options with BST definition

   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, while others describe different or incorrect structures.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option B

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 for BST nodes [OK]

Common Mistakes:

• Thinking BST nodes must have two children
• Confusing BST with binary tree
• Assuming all nodes have same value

2. Which of the following is the correct C# syntax to declare a BST node class with integer value and left/right children?

easy

A. public class Node { public int Value; public Node Left; public Node Right; }

B. class Node { int Value; Node Left, Right; }

C. public struct Node { int Value; Node Left; Node Right; }

D. Node { int Value; Node Left; Node Right; }

Solution

1. Step 1: Check class declaration syntax in C#

   In C#, classes are declared with 'public class ClassName' and members with access modifiers.

2. Step 2: Validate member declarations

   public class Node { public int Value; public Node Left; public Node Right; } correctly declares public fields for value and child nodes. class Node { int Value; Node Left, Right; } misses access modifiers and uses shorthand which is less clear. public struct Node { int Value; Node Left; Node Right; } uses struct which is less common for nodes. Node { int Value; Node Left; Node Right; } is invalid syntax.

3. Final Answer:

   public class Node { public int Value; public Node Left; public Node Right; } -> Option A

4. Quick Check:

   Correct C# class syntax = public class Node { public int Value; public Node Left; public Node Right; } [OK]

Hint: Use 'public class' and public fields for node members [OK]

Common Mistakes:

• Omitting access modifiers
• Using struct instead of class for nodes
• Incorrect class syntax

3. Given the following BST insertion code snippet, what will be the in-order traversal output after inserting values 10, 5, 15, 7?

medium

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

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

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

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

Solution

1. Step 1: Insert values into BST following property

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

2. Step 2: Perform in-order traversal (left, node, right)

   Traverse left subtree: 5 then 7, then root 10, then right subtree 15.

3. Final Answer:

   5 -> 7 -> 10 -> 15 -> null -> Option A

4. Quick Check:

   In-order traversal sorts BST values ascending [OK]

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

Common Mistakes:

• Confusing insertion order with traversal order
• Incorrectly placing 7 in BST
• Mixing traversal types

4. Identify the bug in this BST insertion method snippet:

public Node Insert(Node root, int val) {
  if (root == null) return new Node { Value = val };
  if (val < root.Value) Insert(root.Left, val);
  else Insert(root.Right, val);
  return root;
}

medium

A. The method should return void instead of Node.

B. The base case should return null instead of new Node.

C. The method does not assign the returned node to root.Left or root.Right after recursion.

D. The comparison operator should be val <= root.Value.

Solution

1. Step 1: Analyze recursive calls in insertion

   The recursive calls Insert(root.Left, val) and Insert(root.Right, val) do not update root.Left or root.Right with returned nodes.

2. Step 2: Understand why assignment is needed

   Without assigning, new nodes are created but not linked to the tree, breaking BST structure.

3. Final Answer:

   The method does not assign the returned node to root.Left or root.Right after recursion. -> Option C

4. Quick Check:

   Assign recursive result to child nodes [OK]

Hint: Always assign recursive insert result to child pointers [OK]

Common Mistakes:

• Forgetting to assign recursive call results
• Changing base case incorrectly
• Misunderstanding return types

5. Why is maintaining the BST property important when deleting a node from a BST?

hard

A. To ensure the tree remains balanced and search operations stay efficient.

B. Because BSTs do not allow deletion of nodes without this property.

C. To prevent memory leaks in the program.

D. Because violating the property can cause incorrect search results and break traversal order.

Solution

1. Step 1: Understand BST property role in search and traversal

   The BST property ensures that searching and traversing nodes in order works correctly.

2. Step 2: Analyze effect of violating BST property after deletion

   If the property is broken, search may miss nodes or return wrong results, and in-order traversal won't be sorted.

3. Final Answer:

   Because violating the property can cause incorrect search results and break traversal order. -> Option D

4. Quick Check:

   Maintaining BST property preserves correct search and traversal [OK]

Hint: Keep BST property to keep search and traversal correct [OK]

Common Mistakes:

• Confusing balance with BST property
• Thinking deletion is not allowed
• Assuming memory leaks relate to BST property