Binary search tree in C#

Problem

The price index crawls

The shop's "price from … to …" filter searches a price index, not the whole catalog. The index is a binary tree: every price is a node, cheaper ones on the left, pricier ones on the right. With 1000 shuffled prices the tree has 22 levels, and writing and looking up every price takes 22,990 comparisons in total: about 23 per price.

This morning the supplier changed the format: the feed now arrives sorted by price. The same 1000 prices, the same code, and the comparisons jump to 1,000,000: 43 times more. The tree now has 1000 levels.

Why does the order of the input matter when the prices are the same?

The idea

Smaller to the left, bigger to the right

A binary search tree (BST) is made of nodes with two links each, Left and Right. There is one rule: everything in the left subtree of a node is smaller than it, everything in the right subtree is bigger.

So searching is a binary search without an array: at every node you compare and skip a whole subtree. Adding follows the same path until it reaches an empty spot and hangs the new node there. Nothing moves, unlike inserting into a sorted array.

public bool Add(int price)
{
    Node? parent = null;
    var cur = Root;
    int level = 1;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return false;
        parent = cur;
        cur = price < cur.Price ? cur.Left : cur.Right;
        level++;
    }
    var node = new Node(price);
    if (parent == null) Root = node;
    else if (price < parent.Price) parent.Left = node;
    else parent.Right = node;
    Size++;
    Depth = Math.Max(Depth, level);
    return true;
}

public bool Add(int price)
{
    Node? parent = null;
    var cur = Root;
    int level = 1;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return false;
        parent = cur;
        cur = price < cur.Price ? cur.Left : cur.Right;
        level++;
    }
    var node = new Node(price);
    if (parent == null) Root = node;
    else if (price < parent.Price) parent.Left = node;
    else parent.Right = node;
    Size++;
    Depth = Math.Max(Depth, level);
    return true;
}

public List<int> Sorted()
{
    var output = new List<int>();
    Walk(Root, output);
    return output;
}

private static void Walk(Node? node, List<int> output)
{
    if (node == null) return;
    Walk(node.Left, output);
    output.Add(node.Price);
    Walk(node.Right, output);
}

Step by step, in words

An empty price index. Every price walks down from the root: cheaper goes left, pricier goes right.
49 comes first. The tree is empty, so 49 becomes the root.
12 < 49: left. The spot is empty, so 12 becomes the left child of 49. 89 goes right.
24: cheaper than 49 (left), pricier than 12 (right). Two comparisons, and it lands on level 3.
32: 49, 12, 24, then right. Three comparisons for 7 prices: each one skips a whole subtree.
Walk: left subtree, the node, right subtree. The prices come out sorted: 6 12 24 32 49 89 159.

The number of comparisons is the number of levels on the path. If the tree is low, about log₂ n levels, every search is O(log n).

See it

Your own tree

A node holds the price and the two links:

class Node
{
    public int Price;
    public Node? Left;
    public Node? Right;

    public Node(int price)
    {
        Price = price;
    }
}

add walks down from the root and remembers the last node (parent). Once it reaches an empty spot, it hangs the new node to the left or to the right of parent. The same price does not go in twice. level counts the levels on the way, so the tree knows how deep it is:

public bool Add(int price)
{
    Node? parent = null;
    var cur = Root;
    int level = 1;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return false;
        parent = cur;
        cur = price < cur.Price ? cur.Left : cur.Right;
        level++;
    }
    var node = new Node(price);
    if (parent == null) Root = node;
    else if (price < parent.Price) parent.Left = node;
    else parent.Right = node;
    Size++;
    Depth = Math.Max(Depth, level);
    return true;
}

contains follows the same path, but hangs nothing:

public bool Contains(int price)
{
    var cur = Root;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return true;
        cur = price < cur.Price ? cur.Left : cur.Right;
    }
    return false;
}

The cheapest price is furthest left, the priciest furthest right (the tree is not empty):

public int Min()
{
    var node = Root!;
    while (node.Left != null) node = node.Left;
    return node.Price;
}

public int Max()
{
    var node = Root!;
    while (node.Right != null) node = node.Right;
    return node.Price;
}

In-order traversal: first the left subtree, then the node, then the right subtree. That way the prices come out sorted. It uses recursion here, because every subtree is a tree again:

public List<int> Sorted()
{
    var output = new List<int>();
    Walk(Root, output);
    return output;
}

private static void Walk(Node? node, List<int> output)
{
    if (node == null) return;
    Walk(node.Left, output);
    output.Add(node.Price);
    Walk(node.Right, output);
}

var tree = new PriceTree();
foreach (var price in new[] { 49, 12, 89, 24, 6, 159, 32 })
{
    tree.Add(price);
}
Console.WriteLine($"in order: [{string.Join(", ", tree.Sorted())}]");
Console.WriteLine($"cheapest: {tree.Min()}, priciest: {tree.Max()}");
foreach (var price in new[] { 32, 50 })
{
    tree.Compares = 0;
    bool found = tree.Contains(price);
    Console.WriteLine($"{price}: {(found ? "yes" : "no")}, comparisons: {tree.Compares}");
}

in order: [6, 12, 24, 32, 49, 89, 159]
cheapest: 6, priciest: 159
32: yes, comparisons: 4
50: no, comparisons: 2

32 is found in 4 comparisons: 49, 12, 24, 32. For 50, 2 are enough: 49, then 89, and there is nothing to the left of 89, so 50 is missing.

Try it

How many comparisons?

var tree = new PriceTree();
foreach (var price in new[] { 50, 30, 70, 20, 40, 60, 80 })
{
    tree.Add(price);
}
tree.Compares = 0;
tree.Contains(65);
Console.WriteLine(tree.Compares);

Answer

Try it

Fill in

The cheapest price:

public int Min()
{
    var node = Root!;
    while (node. != null) node = node.Left;
    return node.Price;
}

The idea

Sorted input: the tree becomes a chain

Back to the feed. When the prices arrive sorted, every new one is pricier than all so far. It passes every node on the right and hangs at the far right. Nothing ever goes left, and the tree is a chain: a linked list with useless empty links.

public bool Add(int price)
{
    Node? parent = null;
    var cur = Root;
    int level = 1;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return false;
        parent = cur;
        cur = price < cur.Price ? cur.Left : cur.Right;
        level++;
    }
    var node = new Node(price);
    if (parent == null) Root = node;
    else if (price < parent.Price) parent.Left = node;
    else parent.Right = node;
    Size++;
    Depth = Math.Max(Depth, level);
    return true;
}

Step by step, in words

The supplier feed sends the same 7 prices, but sorted: 6, 12, 24, 32, 49, 89, 159.
Every new price is pricier than all before it, so it always goes right. Nothing ever goes left.
Price number i walks past all i before it: 0 + 1 + … + 6 = 21 comparisons. The tree is a chain of 7 levels.
contains(159) walks all 7 nodes, like a linked list. With 1000 prices: 1000 levels.
The same prices, balanced: 3 levels instead of 7. AVL and red-black trees keep this shape with rotations.

Price number i walks past i nodes. For n prices that is 0 + 1 + … + (n − 1) when writing, and as much again plus n when searching: exactly n² comparisons. It is the same trap as quick sort's bad pivot: sorted input, and the worst case.

The program from the problem: the same 1000 prices, once sorted, once shuffled:

static int[] Shuffled(int n)
{
    var a = new int[n];
    for (int i = 0; i < n; i++) a[i] = 100 + i;
    long x = 2026;
    for (int i = n - 1; i > 0; i--)
    {
        x = x * 48271 % 2147483647;
        int j = (int)(x % (i + 1));
        (a[i], a[j]) = (a[j], a[i]);
    }
    return a;
}

static string Report(int[] prices)
{
    var tree = new PriceTree();
    foreach (var p in prices) tree.Add(p);
    foreach (var p in prices) tree.Contains(p);
    return $"depth {tree.Depth}, comparisons {tree.Compares}";
}

var feed = new int[1000];
for (int i = 0; i < 1000; i++) feed[i] = 100 + i;
Console.WriteLine($"ascending: {Report(feed)}");
Console.WriteLine($"shuffled: {Report(Shuffled(1000))}");

ascending: depth 1000, comparisons 1000000
shuffled: depth 22, comparisons 22990

Run both inputs in the browser:

Prices in shuffled order O(n log n)
Prices in ascending order O(n²)

Algorithm	n = 10	n = 1,000	n = 5,000	n = 100,000
Prices in shuffled order	56	22,990	157,880	4,029,826
Prices in ascending order	100	1,000,000	25,000,000	≈ 10,000,000,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

With shuffled input a search passes on average through about 2 · ln n − 3 nodes (about 12 for 1000 prices), which grows like log n, and everything is O(n log n). With sorted input it is O(n²): for 1000 prices, 1,000,000 comparisons against 22,990. This is the difference between the average and the worst case, and real data is often exactly sorted: by price, by date, by number.

The idea

A balanced tree

Shuffling the input helps, but you can't always do it: the prices arrive one by one while the shop is running. A balanced tree fixes itself: after every add it checks whether one branch has become much longer than the other and rearranges it. That way the height stays O(log n) for any input, and every search, add and remove is O(log n).

The rearranging is a rotation: a node and its child swap places. In a right rotation the left child becomes the parent, the old parent becomes its right child, and the child's right subtree moves to the left of the old parent. The rule "smaller to the left" still holds, and one branch gets one level shorter.

More precisely, if you are curious

A right rotation around 32 in the chain 32 → 24 → 12 (each is the left child of the one before):

      32               24
     /                /  \
   24        →      12    32
   /
 12

24 becomes the root and 32 goes to its right. The sorted order is the same: 12, 24, 32.

AVL (Adelson-Velsky and Landis, 1962) keeps the height of the subtree in every node. If the heights of the two children differ by more than 1, it does one or two rotations. The tree is very low (at most about 1.44 · log₂ n), so searching is fast, but adding sometimes does more work.

A red-black tree colors its nodes and keeps two rules: a red node has no red child, and every path from the root to an empty spot passes through the same number of black nodes. That lets one branch be at most twice as long as another, so the height is at most 2 · log₂ n. Adding and removing need recoloring and at most two or three rotations.

What the languages do:

Java: TreeMap and TreeSet are red-black trees. Besides get and put they have the ordered operations: firstKey, floorKey (the largest up to a given key), subMap(from, to). They order by Comparable or by a Comparator you pass in.
C#: SortedSet<T> is a red-black tree, and SortedDictionary<TKey, TValue> is built on top of it. SortedSet has Min, Max and GetViewBetween(from, to). Watch out for SortedList<TKey, TValue>: it is two sorted arrays, so lookups are O(log n), but adding in the middle is O(n).
Python: there is no built-in balanced tree. The bisect module searches a sorted list in O(log n), but insort inserts in O(n), because it shifts the elements. The sortedcontainers package (SortedList, SortedDict) is installed separately and is not a tree: it keeps a list of sorted lists of about a thousand elements each.
JavaScript: there is no built-in sorted tree. Map and Set keep insertion order, not order by value. What is left is a sorted array with binary search, or a library.

Try it

Find the bug

Someone rewrote Add. Five prices go in, but the traversal shows only some of them, and the search can't find 6 and 24:

public bool Add(int price)
{
    Node? parent = null;
    var cur = Root;
    int level = 1;
    while (cur != null)
    {
        Compares++;
        if (price == cur.Price) return false;
        parent = cur;
        cur = price < cur.Price ? cur.Left : cur.Right;
        level++;
    }
    var node = new Node(price);
    if (parent == null) Root = node;
    else if (price > parent.Price) parent.Left = node;
    else parent.Right = node;
    Size++;
    Depth = Math.Max(Depth, level);
    return true;
}

var tree = new PriceTree();
foreach (var price in new[] { 49, 12, 89, 24, 6 })
{
    tree.Add(price);
}
Console.WriteLine($"in order: [{string.Join(", ", tree.Sorted())}]");
Console.WriteLine($"6: {(tree.Contains(6) ? "yes" : "no")}");
Console.WriteLine($"24: {(tree.Contains(24) ? "yes" : "no")}");

in order: [49, 6]
6: no
24: no

Which line has the bug?

Pick the line with the bug.

Exercise

A price stops being valid

Solve this one in your own editor.

Removing from the index. Add Remove(price), which returns whether it removed a price. There are three cases:

the node is a leaf: just unhook it;
it has one child: the child takes its place;
it has two children: find the next bigger price (the leftmost one in the right subtree), put it in place of the removed one and remove it from the right subtree. It has no left child, so that is one of the first two cases.

Put in the prices 49, 12, 89, 24, 6, 159, 32 and remove 12 (two children), 49 (the root, two children) and 70 (missing):

-12: [6, 24, 32, 49, 89, 159]
-49: [6, 24, 32, 89, 159]
-70: none
root: 89

More tasks

Prices in a range. Write between(from, to), which returns the prices from from to to in order, without walking the whole tree: don't go left from a node smaller than from, nor right from a node bigger than to.
The best within budget. Write floor(budget): the priciest price that is not over the budget. Compare with floorKey in Java or GetViewBetween in C#.
Height with recursion. Write height(node) as 1 + the larger of the two children's heights. Run it on the chain of 1000 sorted prices. What happens in Python? And with 100,000 prices in Java?

Test

Check yourself

1. The tree holds the prices 49, 12, 89, 24, 6, 159 and 32. In what order does an in-order traversal give them?49 12 6 24 32 89 1596 12 24 32 49 89 15949 12 89 24 6 159 32

2. Why is a hash table no good for "all products between €20 and €60", while a tree is?Both work equally wellBecause a hash table is slower at lookupsBecause the hash scatters close prices into random buckets, while the tree keeps them in order

3. A plain binary search tree receives 1000 prices in ascending order. How many levels does it have?About 105001000

4. What is true about TreeMap in Java and SortedDictionary in C#?Both are hash tables with sorted keysBoth are red-black trees: the height stays O(log n) for any inputOnly TreeMap is balanced

Binary search tree

Cookies