BST Property and Why It Matters in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Binary Search Tree (BST) property?

In a BST, for every node, all values in its left subtree are smaller, and all values in its right subtree are larger than the node's value.

beginner

Why does the BST property matter for searching?

Because the BST property keeps values ordered, it allows searching by comparing values and moving left or right, making search faster than checking every node.

beginner

How does the BST property help in inserting a new value?

The BST property guides where to insert a new value by comparing it with nodes and moving left or right until finding the correct empty spot.

intermediate

What happens if the BST property is broken?

If the BST property is broken, searching and inserting become inefficient because the tree loses its order, and operations may take longer.

beginner

Explain the BST property using a real-life example.

Think of a phone book sorted by names: all names before 'John' come before it alphabetically (left), and all after come after (right). This order helps find names quickly, like the BST property.

In a BST, where are values smaller than a node's value located?

A Anywhere in the tree

B In the right subtree

C At the root only

D In the left subtree

By definition, smaller values are in the left subtree of a node.

Why is the BST property important for search speed?

A It allows skipping half the tree at each step

B It keeps the tree balanced

C It stores values randomly

D It uses hashing

The BST property lets us decide to go left or right, skipping half the nodes each time, speeding up search.

What happens if you insert a value larger than a node's value in a BST?

A It goes to the left subtree

B It replaces the node

C It goes to the right subtree

D It is ignored

Larger values go to the right subtree according to the BST property.

If the BST property is broken, what is a likely consequence?

A Searching becomes slower

B Searching becomes faster

C The tree becomes balanced

D Insertion is impossible

Without the BST property, the tree loses order, making search slower.

Which real-life example best illustrates the BST property?

A A shuffled deck of cards

B A sorted phone book

C A random list of names

D A pile of unsorted papers

A sorted phone book keeps names in order, similar to how BST keeps values ordered.

Describe the BST property and explain why it helps in searching and inserting values.

Think about how comparing values decides where to go next.

What problems arise if the BST property is not maintained? Give an example.

Imagine searching in a random list versus a sorted list.

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