Why BST Over Plain Binary Tree in DSA C# - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of numbers and you want to find, add, or check if a number exists quickly. You can store these numbers in a tree structure. A plain binary tree stores numbers without any order, while a Binary Search Tree (BST) keeps numbers in a sorted way.This project will help you see why using a BST is better than a plain binary tree for searching numbers.

🎯 Goal: You will create two trees: a plain binary tree and a BST with the same numbers. Then, you will search for a number in both trees and compare the steps taken. This will show why BST is faster for searching.

📋 What You'll Learn

Create a plain binary tree with specific numbers

Create a BST with the same numbers

Implement a search method for both trees

Compare the search steps for a given number

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find data without checking every item.

💼 Career

Understanding BSTs helps in software development roles where efficient data storage and retrieval are important.

1

Create a plain binary tree with given numbers

Create a class called Node with an int value and two Node references called Left and Right. Then create a plain binary tree with root node value 10, left child 5, and right child 15.

DSA C#

// Define Node class and create plain binary tree root
// Your code here

Hint

Define a Node class with value and two child nodes. Then create the root and its two children.

2

Create a Binary Search Tree (BST) with the same numbers

Create a class called BST with a Node called Root. Add a method Insert(int value) to add numbers following BST rules. Insert the numbers 10, 5, and 15 into the BST.

DSA C#

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

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

Node rootPlain = new Node(10);
rootPlain.Left = new Node(5);
rootPlain.Right = new Node(15);

// Define BST class with Insert method and insert 10, 5, 15
// Your code here

Hint

Create a BST class with an Insert method that adds nodes in order.

3

Implement search methods for both trees

Add a method SearchPlain(Node root, int value) to search the plain binary tree by checking both left and right children recursively. Add a method SearchBST(Node root, int value) to search the BST by comparing values and moving left or right accordingly.

DSA C#

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

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

Node rootPlain = new Node(10);
rootPlain.Left = new Node(5);
rootPlain.Right = new Node(15);

public class BST
{
    public Node Root;

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }
        if (value  root.Value)
            root.Right = InsertRec(root.Right, value);
        return root;
    }
}

BST bst = new BST();
bst.Insert(10);
bst.Insert(5);
bst.Insert(15);

// Add SearchPlain and SearchBST methods below
// Your code here

Hint

Search the plain tree by checking both children. Search the BST by comparing values and choosing left or right.

4

Compare search results for the number 15

Use SearchPlain(rootPlain, 15) and bst.SearchBST(bst.Root, 15) to search for the number 15 in both trees. Print the results as "Plain Tree Found: true/false" and "BST Found: true/false".

DSA C#

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

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

Node rootPlain = new Node(10);
rootPlain.Left = new Node(5);
rootPlain.Right = new Node(15);

public class BST
{
    public Node Root;

    public void Insert(int value)
    {
        Root = InsertRec(Root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }
        if (value  root.Value)
            root.Right = InsertRec(root.Right, value);
        return root;
    }

    public bool SearchBST(Node root, int value)
    {
        if (root == null)
            return false;
        if (root.Value == value)
            return true;
        if (value < root.Value)
            return SearchBST(root.Left, value);
        else
            return SearchBST(root.Right, value);
    }
}

BST bst = new BST();
bst.Insert(10);
bst.Insert(5);
bst.Insert(15);

bool SearchPlain(Node root, int value)
{
    if (root == null)
        return false;
    if (root.Value == value)
        return true;
    return SearchPlain(root.Left, value) || SearchPlain(root.Right, value);
}

// Print search results for 15
// Your code here

Hint

Call the search methods with value 15 and print the results exactly as shown.

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. Because BST keeps elements in sorted order allowing faster search

B. Because BST uses less memory than a plain Binary Tree

C. Because BST nodes can have more than two children

D. Because BST does not require pointers to child nodes

Solution

1. Step 1: Understand the structure difference

   A plain Binary Tree has no order among nodes, while a BST keeps nodes sorted so left child is smaller and right child is larger.

2. Step 2: Analyze search efficiency

   Because of this order, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, unlike plain Binary Tree which may require checking all nodes.

3. Final Answer:

   Because BST keeps elements in sorted order allowing faster search -> Option A

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST keeps data sorted for quick searching [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing BST with trees having multiple children
• Assuming BST nodes don't have child pointers

2. Which of the following is the correct syntax to declare a node class for a BST in C#?

easy

A. public class Node { public int data; public Node left, right; }

B. class Node { int data; Node left, right; }

C. public struct Node { int data; Node left, right; }

D. public class Node { int data; Node left; Node right; }

Solution

1. Step 1: Check access modifiers and data types

   For BST node, data and child pointers should be accessible, so public fields are preferred for simplicity.

2. Step 2: Verify syntax correctness

   public class Node { public int data; public Node left, right; } correctly declares a public class with public int data and two child nodes left and right of type Node.

3. Final Answer:

   public class Node { public int data; public Node left, right; } -> Option A

4. Quick Check:

   Public class with public fields = correct BST node [OK]

Hint: Use public class with public fields for BST node [OK]

Common Mistakes:

• Using struct instead of class for nodes
• Missing public keyword for fields
• Declaring multiple lines instead of combined declaration

3. What will be the output of the following C# code that inserts values into a BST and then performs an inorder traversal?

class Node {
  public int data; public Node left, right;
  public Node(int val) { data = val; left = right = null; }
}
class BST {
  public Node root;
  public void Insert(int val) {
    root = InsertRec(root, val);
  }
  private Node InsertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = InsertRec(root.left, val);
    else root.right = InsertRec(root.right, val);
    return root;
  }
  public void Inorder(Node root) {
    if (root != null) {
      Inorder(root.left);
      Console.Write(root.data + " ");
      Inorder(root.right);
    }
  }
}

var tree = new BST();
tree.Insert(10);
tree.Insert(5);
tree.Insert(15);
tree.Inorder(tree.root);

medium

A. 10 5 15

B. 5 10 15

C. 15 10 5

D. 5 15 10

Solution

1. Step 1: Insert nodes into BST

   Insert 10 as root, then 5 goes to left of 10, 15 goes to right of 10.

2. Step 2: Perform inorder traversal

   Inorder visits left subtree, root, then right subtree. So output is 5 (left), 10 (root), 15 (right).

3. Final Answer:

   5 10 15 -> Option B

4. Quick Check:

   Inorder traversal of BST = sorted order [OK]

Hint: Inorder traversal of BST prints sorted values [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Inserting nodes incorrectly
• Printing nodes in wrong order

4. The following code attempts to insert nodes into a BST but has a bug. What is the bug?

class Node {
  public int data; public Node left, right;
  public Node(int val) { data = val; }
}
class BST {
  public Node root;
  public void Insert(int val) {
    root = InsertRec(root, val);
  }
  private Node InsertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = InsertRec(root.left, val);
    else root.right = InsertRec(root.right, val);
    return root;
  }
}

medium

A. root is not initialized before insertion

B. InsertRec method has wrong return type

C. Node constructor does not initialize left and right pointers

D. Missing public keyword for Insert method

Solution

1. Step 1: Check Node constructor

   The constructor sets data but does not initialize left and right pointers to null.

2. Step 2: Verify standard practice for trees

   Node constructors in tree implementations must explicitly set left = right = null; for proper initialization and to avoid potential issues.

3. Final Answer:

   Node constructor does not initialize left and right pointers -> Option C

4. Quick Check:

   Uninitialized child pointers cause runtime errors [OK]

Hint: Always initialize child pointers in node constructor [OK]

Common Mistakes:

• Assuming null pointers cause compile errors
• Ignoring default null initialization in C#
• Confusing method return types

5. You want to store a large collection of unique numbers and perform frequent searches. Why would using a BST be better than a plain Binary Tree, and what is the worst-case time complexity difference?

hard

A. BST nodes have more children, reducing tree height; plain Binary Tree nodes have only two children

B. BST uses less memory, so search is faster; plain Binary Tree uses more memory

C. BST allows duplicate values for faster search; plain Binary Tree does not

D. BST keeps data sorted, allowing average O(log n) search; plain Binary Tree search is O(n)

Solution

1. Step 1: Understand BST advantages

   BST keeps nodes sorted, so searching can skip half the tree at each step, giving average O(log n) time.

2. Step 2: Compare with plain Binary Tree

   Plain Binary Tree has no order, so search may check all nodes, resulting in O(n) time in worst case.

3. Final Answer:

   BST keeps data sorted, allowing average O(log n) search; plain Binary Tree search is O(n) -> Option D

4. Quick Check:

   BST sorted = O(log n) search, plain tree = O(n) [OK]

Hint: BST sorted structure gives faster search than plain tree [OK]

Common Mistakes:

• Thinking BST uses less memory
• Believing BST allows duplicates for speed
• Confusing number of children per node