Binary Search Trees

A Binary Search Tree (BST) is a binary tree with an ordering property: for every node, all values in the left subtree are less than the node, and all values in the right subtree are greater.

Why BSTs?

This property enables O(log n) average-case search, insert, and delete — much faster than linear search through a list.

BST Implementation

public class BST
{
    private TreeNode<int>? root;

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

    private TreeNode<int> Insert(TreeNode<int>? node, int value)
    {
        if (node == null) return new TreeNode<int>(value);

        if (value < node.Value)
            node.Left = Insert(node.Left, value);
        else if (value > node.Value)
            node.Right = Insert(node.Right, value);

        return node;
    }

    public bool Contains(int value)
    {
        return Contains(root, value);
    }

    private bool Contains(TreeNode<int>? node, int value)
    {
        if (node == null) return false;
        if (value == node.Value) return true;

        return value < node.Value
            ? Contains(node.Left, value)
            : Contains(node.Right, value);
    }
}

Usage

var bst = new BST();
bst.Insert(5);
bst.Insert(3);
bst.Insert(7);
bst.Insert(1);
bst.Insert(4);

Console.WriteLine(bst.Contains(4)); // True
Console.WriteLine(bst.Contains(6)); // False

Complexity

Worst case happens when elements are inserted in sorted order, creating a linked list. Self-balancing trees (AVL, Red-Black) solve this by keeping the tree balanced after every operation.