BST Property and Why It Matters in DSA C# - Build from Scratch

BST Property and Why It Matters

📖 Scenario: Imagine you are organizing a collection of books by their unique ID numbers. You want to store them so that finding any book is quick and easy. A Binary Search Tree (BST) helps you do this by keeping books in order.

🎯 Goal: You will build a simple Binary Search Tree (BST) with three nodes and learn how the BST property keeps the tree organized. Then, you will print the tree nodes in order to see the sorted result.

📋 What You'll Learn

Create a BST node class with integer value and left/right child references

Manually create a BST with root and two child nodes following BST property

Write a method to do in-order traversal to print nodes in sorted order

Print the values of the BST nodes in ascending order

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to keep data sorted and allow fast searching, like finding a book in a library quickly.

💼 Career

Understanding BSTs is important for software developers working on search engines, data storage, and any application needing efficient data lookup.

1

Create BST Node Class and Root Node

Create a class called BSTNode with an integer property Value, and two BSTNode properties called Left and Right. Then create a BSTNode variable called root with Value 10 and Left and Right set to null.

DSA C#

// Define BSTNode class and create root node with value 10
// Your code here

Hint

Define a class with properties for value and child nodes. Then create the root node with value 10.

2

Add Left and Right Child Nodes Following BST Property

Add two child nodes to root: set root.Left to a new BSTNode with Value 5, and set root.Right to a new BSTNode with Value 15. This keeps the BST property where left child is less than root and right child is greater.

DSA C#

public class BSTNode
{
    public int Value;
    public BSTNode Left;
    public BSTNode Right;

    public BSTNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

BSTNode root = new BSTNode(10);
// Add left child with value 5 and right child with value 15
// Your code here

Hint

Assign new BSTNode objects with values 5 and 15 to root's left and right properties.

3

Write In-Order Traversal Method

Write a method called InOrderTraversal that takes a BSTNode parameter called node. It should recursively visit the left child, print the node's Value, then visit the right child. Use Console.Write to print values followed by a space.

DSA C#

public class BSTNode
{
    public int Value;
    public BSTNode Left;
    public BSTNode Right;

    public BSTNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

BSTNode root = new BSTNode(10);
root.Left = new BSTNode(5);
root.Right = new BSTNode(15);

// Write InOrderTraversal method here
// Your code here

Hint

Use recursion to visit left child, print value, then right child. Check for null node to stop.

4

Print BST Nodes in Sorted Order

In the Main method, call InOrderTraversal with root as argument. This will print the BST node values in ascending order.

DSA C#

using System;

public class BSTNode
{
    public int Value;
    public BSTNode Left;
    public BSTNode Right;

    public BSTNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

class Program
{
    static void InOrderTraversal(BSTNode node)
    {
        if (node == null) return;
        InOrderTraversal(node.Left);
        Console.Write(node.Value + " ");
        InOrderTraversal(node.Right);
    }

    static void Main()
    {
        BSTNode root = new BSTNode(10);
        root.Left = new BSTNode(5);
        root.Right = new BSTNode(15);

        // Call InOrderTraversal here
        // Your code here
    }
}

Hint

Simply call InOrderTraversal(root); inside Main to print the sorted values.

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