BST Property and Why It Matters in DSA C#

Mental Model

A Binary Search Tree keeps smaller values on the left and bigger values on the right, making searching fast.

Analogy: Think of a phone book where names are sorted alphabetically; you look left for names before and right for names after, so you find a name quickly.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: BST with nodes 5, 3, 7, 2, 4, 8; search for value 4

Goal: Show how BST property helps find 4 quickly by deciding left or right at each step

Step 1: Start at root node 5

      [5↑]
     /   \
    3     7
   / \     \
  2   4     8

Why: We begin search at the top of the tree

Step 2: Compare 4 with 5, 4 is less, go left to node 3

      5
     /   \
   [3↑]   7
   / \     \
  2   4     8

Why: Because 4 < 5, BST property says 4 must be in left subtree

Step 3: Compare 4 with 3, 4 is greater, go right to node 4

      5
     /   \
    3     7
   / \     \
  2  [4↑]  8

Why: Because 4 > 3, BST property says 4 must be in right subtree of 3

Step 4: Found node 4, stop search

      5
     /   \
    3     7
   / \     \
  2  [4↑]  8

Why: We found the value, search ends

Result:

      5
     /   \
    3     7
   / \     \
  2   4     8
Answer: Found 4

Annotated Code

DSA C#

using System;

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

class BST {
    public Node root;

    public BST() { root = null; }

    public void Insert(int val) {
        root = InsertRec(root, val);
    }

    private Node InsertRec(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = InsertRec(node.left, val);
        else node.right = InsertRec(node.right, val);
        return node;
    }

    public bool Search(int val) {
        return SearchRec(root, val);
    }

    private bool SearchRec(Node node, int val) {
        if (node == null) return false; // reached leaf, not found
        if (val == node.val) return true; // found value
        if (val < node.val) return SearchRec(node.left, val); // go left
        else return SearchRec(node.right, val); // go right
    }

    public void PrintInOrder() {
        PrintInOrderRec(root);
        Console.WriteLine("null");
    }

    private void PrintInOrderRec(Node node) {
        if (node == null) return;
        PrintInOrderRec(node.left);
        Console.Write(node.val + " -> ");
        PrintInOrderRec(node.right);
    }
}

class Program {
    static void Main() {
        BST tree = new BST();
        int[] values = {5, 3, 7, 2, 4, 8};
        foreach (int v in values) tree.Insert(v);

        tree.PrintInOrder();

        int searchVal = 4;
        bool found = tree.Search(searchVal);
        Console.WriteLine(found ? $"Found {searchVal}" : $"{searchVal} not found");
    }
}

if (node == null) return false; // reached leaf, not found

stop search if reached empty spot

if (val == node.val) return true; // found value

found the value, return true

if (val < node.val) return SearchRec(node.left, val); // go left

go left subtree if value is smaller

else return SearchRec(node.right, val); // go right

go right subtree if value is bigger

Output

2 -> 3 -> 4 -> 5 -> 7 -> 8 -> null

Found 4

Complexity Analysis

Time: O(h) where h is tree height, because search follows one path down the tree

Space: O(h) due to recursion stack in worst case

vs Alternative: Compared to searching an unsorted tree or list which is O(n), BST search is faster if tree is balanced

Edge Cases

Empty tree

Search returns false immediately

DSA C#

if (node == null) return false; // reached leaf, not found

Value not in tree

Search reaches null leaf and returns false

DSA C#

if (node == null) return false; // reached leaf, not found

Value is root

Search finds value immediately at root

DSA C#

if (val == node.val) return true; // found value

When to Use This Pattern

When you need fast search, insert, or delete in sorted data, look for BST property to guide efficient tree traversal.

Common Mistakes

Mistake: Not comparing values correctly to decide left or right subtree
Fix: Always compare search value with current node and go left if smaller, right if bigger

Summary

It keeps smaller values left and bigger values right to speed up search.

Use it when you want to find values quickly in a sorted way.

The key is using the value comparison to decide which side to go next.

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