I've noticed a recurring pattern when developers first dive into tree structures: they assume that a Binary Search Tree (BST) is simply a binary tree where the data happens to be sorted. It sounds like a semantic nuance, but it's actually a fundamental misunderstanding of how the data structure functions.

It's not just "sorted"—the Invariant is everything

If you just take a sorted list of numbers and shove them into a binary tree structure without following the BST rules, you don't have a search tree; you have a very expensive linked list. For example, if you insert the numbers 10, 20, and 30 in that order into a naive tree without the "Left < Root < Right" invariant, you'll end up with a long chain leaning entirely to the right. Your search time drops from $O(\log n)$ to $O(n)$. You've lost the entire point of the structure.

The "magic" of the BST isn't that the tree is sorted, but that every single node maintains a strict contract: every node in its left subtree must be smaller, and every node in its right subtree must be larger. This contract allows us to discard half the remaining tree with every single comparison. I always tell my juniors to think of it like a high-stakes game of "Higher or Lower."

Structuring the Node and the Recursive Insert

To build this in C#, we need a node class that can hold a value and references to its two potential children. I prefer using a generic type T here, but since we need to compare values, we have to constrain T to IComparable. Otherwise, the compiler will have no idea how to determine if one "Product" or "Employee" is "less than" another.

public class BSTNode<T> where T : IComparable<T>
{
    public T Value { get; set; }
    public BSTNode<T> Left { get; set; }
    public BSTNode<T> Right { get; set; }

    public BSTNode(T value)
    {
        Value = value;
    }
}

Now, for the insertion. The trick is to use recursion. We start at the root; if the new value is smaller than the current node, we go left. If it's larger, we go right. We keep doing this until we find an empty slot (a null child). I like to handle the root separately to keep the recursive method clean.

public class BinarySearchTree<T> where T : IComparable<T>
{
    private BSTNode<T> _root;

    public void Insert(T value)
    {
        _root = InsertRecursive(_root, value);
    }

    private BSTNode<T> InsertRecursive(BSTNode<T> current, T value)
    {
        if (current == null)
        {
            return new BSTNode<T>(value);
        }

        int comparison = value.CompareTo(current.Value);

        if (comparison < 0)
        {
            current.Left = InsertRecursive(current.Left, value);
        }
        else if (comparison > 0)
        {
            current.Right = InsertRecursive(current.Right, value);
        }
        // If comparison == 0, the value already exists. 
        // In a standard BST, we usually just ignore duplicates.

        return current;
    }
}

Leveraging the Structure for $O(\log n)$ Lookups

Searching is where the payoff happens. Because we maintained that strict invariant during insertion, we don't have to check every node. We just navigate the path. If we're looking for "Employee ID 502" and the current node is "Employee ID 700", we know with absolute certainty that 502 cannot possibly be in the right subtree. We ignore that entire half of the data structure.

public bool Contains(T value)
{
    return SearchRecursive(_root, value);
}

private bool SearchRecursive(BSTNode<T> current, T value)
{
    if (current == null) return false;

    int comparison = value.CompareTo(current.Value);

    if (comparison == 0) return true;
    
    return comparison < 0 
        ? SearchRecursive(current.Left, value) 
        : SearchRecursive(current.Right, value);
}

One quick tip: while this basic implementation is great for learning, in a real-world production system, you'd likely use a "Balanced" BST (like an AVL tree or a Red-Black tree). Why? Because if your data arrives already sorted, our basic BST becomes that "expensive linked list" I mentioned earlier. Balancing ensures the tree stays bushy, keeping your performance consistent.

📋 Practical Task

Build a High-Score Leaderboard using a BST

You are tasked with creating a simple high-score tracking system for a game. Instead of using a List and sorting it every time a new score is added, you will implement a Binary Search Tree to store the scores.

Requirements:

• Create a class ScoreNode that holds an integer Score and a string PlayerName.
• Implement a ScoreTree class that allows you to AddScore(int score, string name).
• The tree should be ordered by the Score (descending or ascending is fine, as long as it is consistent).
• Implement a method FindPlayerByScore(int score) that returns the name of the player who achieved that score. If the score isn't in the tree, return "No player found".
• Challenge: Implement a method PrintAllScores() that performs an In-Order Traversal to print all scores in the leaderboard from lowest to highest.