Trees and Binary Search Trees: Insert, Delete and Traversal in C#

Version note: The code in this post was built with .NET 10, C# 14 and ASP.NET Core 10 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

Bookstore's stock service keeps product IDs in a binary search tree it wrote itself. The same 10,000 IDs are loaded in two ways: one day in random order, the next day sorted, straight from the database with ORDER BY Id. Both trees hold the same 10,000 IDs.

What is the height of each tree? If 1,000 lookups take around 20 µs in the tree built in random order, how long do they take in the tree built in sorted order?

Tree Terms and the BST Rule

A tree is an acyclic, hierarchical structure in which each node has zero or more children. The top node is the root, nodes without children are leaves. A node's depth is the number of edges from the root to it; the tree's height is the number of levels down to the deepest leaf. In a binary tree each node has at most two children: left and right.

A binary search tree (BST) adds a single rule: for every node, all values in the left subtree are smaller than the node and all values in the right subtree are larger. The word "all" matters; not just the direct children but the whole subtree. Thanks to this rule a lookup eliminates one half at every step, like binary search: if the value is smaller than the node, there is no need to look at the right subtree at all.

namespace Algorithms.Trees;

public sealed class TreeNode<T>(T value)
{
    public T Value { get; set; } = value;
    public TreeNode<T>? Left { get; set; }
    public TreeNode<T>? Right { get; set; }
}

Insert and Find

// left subtree < node < right subtree, for every node; duplicates are ignored
public sealed class BinarySearchTree<T>(IComparer<T>? comparer = null)
{
    private readonly IComparer<T> _comparer = comparer ?? Comparer<T>.Default;

    public TreeNode<T>? Root { get; private set; }
    public int Count { get; private set; }

    public bool Insert(T value)
    {
        if (Root is null)
        {
            Root = new TreeNode<T>(value);
            Count = 1;
            return true;
        }
        // iterative: a degenerate tree can be thousands of levels deep
        TreeNode<T> node = Root;
        while (true)
        {
            int cmp = _comparer.Compare(value, node.Value);
            if (cmp == 0) return false;
            if (cmp < 0)
            {
                if (node.Left is null) { node.Left = new TreeNode<T>(value); break; }
                node = node.Left;
            }
            else
            {
                if (node.Right is null) { node.Right = new TreeNode<T>(value); break; }
                node = node.Right;
            }
        }
        Count++;
        return true;
    }

    public bool Contains(T value)
    {
        TreeNode<T>? node = Root;
        while (node is not null)
        {
            int cmp = _comparer.Compare(value, node.Value);
            if (cmp == 0) return true;
            node = cmp < 0 ? node.Left : node.Right;
        }
        return false;
    }
}

Both start at the root and follow a single path, going left or right at each step; the cost is the height of the tree, O(h). If the tree is balanced, h ≈ log₂ n, about 20 steps for 1 million nodes. We wrote insert iteratively because h depends on the insertion order; we will see shortly why that matters. Ignoring duplicates is a design decision. SortedSet<T> does the same and Add returns false. If we wanted to allow duplicates, we would keep a counter in each node.

The Three Cases of Delete

Delete is the operation people get wrong most often in a BST, because there are three separate cases depending on the number of children of the node being removed:

public bool Remove(T value)
{
    int before = Count;
    Root = Remove(Root, value);
    return Count < before;
}

// returns the new root of this subtree
private TreeNode<T>? Remove(TreeNode<T>? node, T value)
{
    if (node is null) return null;
    int cmp = _comparer.Compare(value, node.Value);
    if (cmp < 0) { node.Left = Remove(node.Left, value); return node; }
    if (cmp > 0) { node.Right = Remove(node.Right, value); return node; }

    // found it
    if (node.Left is null) { Count--; return node.Right; }   // case 1 and 2: no child or only right
    if (node.Right is null) { Count--; return node.Left; }   // case 2: only left

    // case 3: two children. The in-order successor (smallest in the right subtree) takes its place.
    TreeNode<T> successor = node.Right;
    while (successor.Left is not null) successor = successor.Left;
    node.Value = successor.Value;
    node.Right = Remove(node.Right, successor.Value); // successor has no left child: case 1 or 2
    return node;
}

When a leaf is removed, cutting it off its parent is enough. When a node with one child is removed, the child takes its place; the BST rule is not broken, because that child's whole subtree is already on the correct side of the node's parent. For a node with two children, the only value that can take its place is the smallest value larger than it: the in-order successor, the leftmost node of the right subtree. Its value is copied into the removed node, then the successor is removed from the right subtree. Since the successor cannot have a left child, this second removal is always case 1 or 2. Symmetrically, the in-order predecessor (the largest in the left subtree) could be used as well.

The "return the new root of this subtree" style solves every case in a single method without keeping a separate reference to the parent; it is the tree counterpart of the sentinel idea from the series' linked list post. The tests check the three cases separately on the post's sample tree and then compare 5,000 random insert/remove operations with a SortedSet<int>:

//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80
//            \
//             65
private static BinarySearchTree<int> Sample() => Build(50, 30, 70, 20, 40, 60, 80, 65);

[Fact]
public void Remove_NodeWithTwoChildren_UsesInOrderSuccessor()
{
    BinarySearchTree<int> tree = Sample();

    Assert.True(tree.Remove(50));

    Assert.Equal(60, tree.Root!.Value);
    Assert.Equal(65, tree.Root.Right!.Left!.Value);
    Assert.Equal([20, 30, 40, 60, 65, 70, 80], Traversal.InOrderIterative(tree.Root));
    Assert.True(BstValidator.IsValid(tree.Root));
    Assert.Equal(7, tree.Count);
}

[Fact]
public void RandomOperations_MatchSortedSet()
{
    BinarySearchTree<int> tree = new();
    SortedSet<int> reference = [];
    Random random = new(5);
    for (int i = 0; i < 5_000; i++)
    {
        int value = random.Next(300);
        if (random.Next(3) == 0) Assert.Equal(reference.Remove(value), tree.Remove(value));
        else Assert.Equal(reference.Add(value), tree.Insert(value));
    }

    Assert.Equal(reference, Traversal.InOrderIterative(tree.Root));
    Assert.True(BstValidator.IsValid(tree.Root));
}

When 50 is removed, the successor 60 moves up to the root and 60's only child, 65, becomes 70's left child; the test's second assert checks exactly that.

Traversal: In, Pre, Post and Level Order

There are four classic ways to walk a tree, and each has its own use. In-order (left, node, right) gives the values of a BST in sorted order. Pre-order (node, left, right) is for copying or serializing a tree; because you write the node before its children, inserting in the same order rebuilds the same tree. Post-order (left, right, node) is for when children must be processed before the node: computing folder sizes, deleting a tree bottom-up. Level-order walks level by level; it uses a queue and is the tree form of BFS (Breadth-First Search) from the series' graph post.

public static List<T> InOrderRecursive<T>(TreeNode<T>? root)
{
    List<T> result = [];
    Visit(root);
    return result;

    void Visit(TreeNode<T>? node)
    {
        if (node is null) return;
        Visit(node.Left);
        result.Add(node.Value);
        Visit(node.Right);
    }
}

public static List<T> InOrderIterative<T>(TreeNode<T>? root)
{
    List<T> result = [];
    Stack<TreeNode<T>> stack = new();
    TreeNode<T>? node = root;
    while (node is not null || stack.Count > 0)
    {
        while (node is not null) // go as far left as possible, remembering the path
        {
            stack.Push(node);
            node = node.Left;
        }
        node = stack.Pop();
        result.Add(node.Value);
        node = node.Right;
    }
    return result;
}

public static List<T> PostOrder<T>(TreeNode<T>? root)
{
    // pre-order with children swapped (node, right, left), reversed = (left, right, node)
    List<T> result = [];
    if (root is null) return result;
    Stack<TreeNode<T>> stack = new([root]);
    while (stack.TryPop(out TreeNode<T>? node))
    {
        result.Add(node.Value);
        if (node.Left is not null) stack.Push(node.Left);
        if (node.Right is not null) stack.Push(node.Right);
    }
    result.Reverse();
    return result;
}

public static List<List<T>> LevelOrder<T>(TreeNode<T>? root)
{
    List<List<T>> levels = [];
    if (root is null) return levels;
    Queue<TreeNode<T>> queue = new([root]);
    while (queue.Count > 0)
    {
        List<T> level = [];
        for (int i = queue.Count; i > 0; i--)
        {
            TreeNode<T> node = queue.Dequeue();
            level.Add(node.Value);
            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        levels.Add(level);
    }
    return levels;
}

Iterative in-order is a subtler example of the conversion from the series' fifth post: in the recursive version the call stack holds the information "write the node when the left subtree is done". In the iterative version the nodes on the explicit stack hold the same information; it pushes the path while going as far left as possible, pops and writes when the left side is done, and moves right. The for (int i = queue.Count; ...) loop in level-order reads the queue's current size once and processes exactly one level; the standard way to separate levels into their own lists. The orders are written out one by one in the test:

[Fact]
public void Traversals_ReturnExpectedOrders()
{
    BinarySearchTree<int> tree = Sample();

    Assert.Equal([20, 30, 40, 50, 60, 65, 70, 80], Traversal.InOrderRecursive(tree.Root));
    Assert.Equal(Traversal.InOrderRecursive(tree.Root), Traversal.InOrderIterative(tree.Root));
    Assert.Equal([50, 30, 20, 40, 70, 60, 65, 80], Traversal.PreOrder(tree.Root));
    Assert.Equal([20, 40, 30, 65, 60, 80, 70, 50], Traversal.PostOrder(tree.Root));
    Assert.Equal([[50], [30, 70], [20, 40, 60, 80], [65]], Traversal.LevelOrder(tree.Root));
    Assert.Equal(4, tree.Height());
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.BinarySearchTreeTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (600ms)

Test run summary: Passed!
  total: 8
  failed: 0
  succeeded: 8

Sorted Inserts and the Degenerate Tree

Back to the opening question. Every value inserted in the order 1, 2, 3, ... is larger than the previous one, so it always goes to the right. The result is a tree where each node has only a right child; in effect, a linked list. The test measures it:

[Fact]
public void SortedInserts_ProduceDegenerateTree()
{
    BinarySearchTree<int> sorted = Build([.. Enumerable.Range(1, 1_000)]);
    Random random = new(3);
    BinarySearchTree<int> shuffled = Build([.. Enumerable.Range(1, 1_000).OrderBy(_ => random.Next())]);

    Assert.Equal(1_000, sorted.Height());
    Assert.InRange(shuffled.Height(), 10, 30);
}

The same 1,000 values: height 1,000 in sorted order, between 10 and 30 in random order. The expected height of a randomly built BST is O(log n), but it is not balanced; it is a few times the best case of log₂ 1,000 ≈ 10. The benchmark runs the same 1,000 lookups on both trees:

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method            | N     | Mean        | Ratio  | Allocated |
|------------------ |------ |------------:|-------:|----------:|
| RandomInsertOrder | 1000  |    12.09 us |   1.00 |         - |
| SortedInsertOrder | 1000  |   327.69 us |  27.10 |         - |
|                   |       |             |        |           |
| RandomInsertOrder | 10000 |    18.41 us |   1.00 |         - |
| SortedInsertOrder | 10000 | 4,071.32 us | 221.23 |         - |

With 10,000 IDs, 1,000 lookups take 18 µs in the tree built in random order and 4.1 ms in the one built in sorted order: 221 times. When N grows 10 times, the random tree's time rises by only 50 percent (log n growth), the degenerate tree's by 12 times (n growth). Same data, same code; the only difference is the insertion order. The measurement ran while other work was running on the machine.

The degenerate tree has a second cost: recursive traversals and the recursive Remove use as many call stack frames as the depth. Calling InOrderRecursive on a tree built from 1 million sorted IDs is exactly the stack overflow from the series' fifth post. That is why we wrote Insert, Contains and Height iteratively. The real fix is keeping the tree balanced: AVL (Adelson-Velsky and Landis) and red-black trees keep the height at O(log n) with rotations after every insert and delete. .NET's SortedSet<T> and SortedDictionary<TKey, TValue> are red-black trees; that is the subject of the series' next post.

A Real Scenario: a Tree from a Flat Category Table

The tree you build most often in production is not a BST but a hierarchy from a flat table in the database. Bookstore's categories live in a Categories(Id, ParentId, Name) table; root categories have a null ParentId. The admin panel and the shop menu want these rows as a nested JSON (JavaScript Object Notation) tree.

The first solution that comes to mind is to scan all rows for each category to find its children; n² comparisons for n categories. The right solution is two passes with a Dictionary: first create a node for each row and store it by Id, then add each node to its parent's child list. The order of the rows does not matter; it works even if a child comes before its parent.

namespace Algorithms.Trees;

// one row of the Categories table
public sealed record CategoryRow(int Id, int? ParentId, string Name);

public sealed class CategoryNode(int id, string name)
{
    public int Id { get; } = id;
    public string Name { get; } = name;
    public List<CategoryNode> Children { get; } = [];
}

public sealed class InvalidCategoryTreeException(string message) : Exception(message);

public static class CategoryTreeBuilder
{
    // O(n): one pass to create nodes, one pass to attach each node to its parent
    public static List<CategoryNode> Build(IReadOnlyList<CategoryRow> rows)
    {
        Dictionary<int, CategoryNode> byId = new(rows.Count);
        foreach (CategoryRow row in rows)
            byId.Add(row.Id, new CategoryNode(row.Id, row.Name));

        List<CategoryNode> roots = [];
        foreach (CategoryRow row in rows)
        {
            CategoryNode node = byId[row.Id];
            if (row.ParentId is null)
                roots.Add(node);
            else if (byId.TryGetValue(row.ParentId.Value, out CategoryNode? parent))
                parent.Children.Add(node);
            else
                throw new InvalidCategoryTreeException($"Category {row.Id} points to missing parent {row.ParentId}.");
        }

        // every node must be reachable from a root; nodes in a ParentId cycle are not
        int reachable = 0;
        Stack<CategoryNode> pending = new(roots);
        while (pending.TryPop(out CategoryNode? node))
        {
            reachable++;
            foreach (CategoryNode child in node.Children) pending.Push(child);
        }
        if (reachable != rows.Count)
        {
            int[] stuck = [.. rows.Select(r => r.Id).Except(Reachable(roots))];
            throw new InvalidCategoryTreeException($"ParentId cycle among categories: {string.Join(", ", stuck)}.");
        }
        return roots;
    }
}

The last block is the price of not trusting the data itself. If an admin accidentally sets 7's parent to 8 and 8's parent to 7, the two categories form a cycle not attached to any root. A recursive menu renderer that enters that cycle either loops forever or dies with a stack overflow. Counting the nodes reachable from the roots with an iterative walk catches the cycle in O(n). Reachable is a small helper that does the same walk, returning Ids with yield return.

[Fact]
public void Build_ParentIdCycle_Throws()
{
    CategoryRow[] rows = [new(1, null, "Books"), new(7, 8, "Loop A"), new(8, 7, "Loop B")];

    InvalidCategoryTreeException ex = Assert.Throws<InvalidCategoryTreeException>(() => CategoryTreeBuilder.Build(rows));
    Assert.Equal("ParentId cycle among categories: 7, 8.", ex.Message);
}

Serving this from an ASP.NET Core minimal API (Application Programming Interface) endpoint takes a few lines. The repository runs a single flat query (no recursive query in the database), and the tree is built in memory:

using Algorithms.Trees;

WebApplicationBuilder builder = WebApplication.CreateBuilder(args);
builder.Services.AddSingleton<ICategoryRepository, InMemoryCategoryRepository>();
WebApplication app = builder.Build();

app.MapGet("/api/categories/tree", async (ICategoryRepository repository, CancellationToken ct) =>
{
    IReadOnlyList<CategoryRow> rows = await repository.GetAllAsync(ct); // one flat query, no recursion in SQL
    try
    {
        return Results.Ok(CategoryTreeBuilder.Build(rows));
    }
    catch (InvalidCategoryTreeException ex)
    {
        return Results.Problem(ex.Message, statusCode: StatusCodes.Status500InternalServerError);
    }
});

app.Run();

$ curl -i http://127.0.0.1:5311/api/categories/tree
HTTP/1.1 200 OK
Content-Type: application/json; charset=utf-8
Date: Sun, 08 Nov 2026 09:06:50 GMT
Server: Kestrel
Transfer-Encoding: chunked

[{"id":1,"name":"Books","children":[{"id":2,"name":"Fiction","children":[{"id":4,"name":"Science Fiction","children":[]}]},{"id":3,"name":"Non-Fiction","children":[{"id":5,"name":"Software","children":[]}]}]},{"id":6,"name":"Gifts","children":[]}]

The InMemoryCategoryRepository in the example returns six fixed rows; in a real application this is a single SELECT Id, ParentId, Name FROM Categories with Entity Framework Core (EF Core) or Dapper. Every node of the resulting JSON has the same shape (id, name, children); on the Angular side it maps directly onto a recursive tree component that renders itself for its children. Endpoint design details are in the ASP.NET Core Web API series post "ASP.NET Core Minimal APIs with .NET 6: MapGet, MapPost and How They Compare to Controllers". The benchmark comparing the Dictionary build with the n² version:

| Method     | N     | Mean         | Ratio | Allocated  |
|----------- |------ |-------------:|------:|-----------:|
| Dictionary | 1000  |     30.58 us |  1.00 |  132.38 KB |
| Quadratic  | 1000  |    391.34 us | 12.81 |  101.79 KB |
|            |       |              |       |            |
| Dictionary | 10000 |    733.92 us |  1.00 | 1287.22 KB |
| Quadratic  | 10000 | 72,151.19 us | 98.49 | 1010.08 KB |

The gap is 13 times at 1,000 categories and 98 times at 10,000: 0.73 ms for the Dictionary version, 72 ms for the n² one. The number of categories grew 10 times; the n² version's time grew 184 times. The Dictionary's price is roughly 27 percent more memory, negligible for a tree built once per request. The measurement ran while other work was running on the machine. If the category table rarely changes, caching the built tree removes even this per-request cost.

In Production

Do not put your own BST in production; an unbalanced BST's performance depends entirely on insertion order, and insertion order is usually not under your control. If you need a sorted set or dictionary, use SortedSet<T> and SortedDictionary<TKey, TValue>; both are balanced and O(log n) in the worst case. The choice is in the C# Collections series post "Sorted Collections in C#: SortedList, SortedDictionary, SortedSet and IComparer".

Put an upper bound on depth in hierarchical data. A category menu should not go beyond 5 levels; an import that sees a record at level 20 should reject it. That is both a user experience decision and a safety limit that protects the call stack of recursive code.

Decide consciously whether to build the tree in the database or in the application. If the whole tree is a few thousand rows, a single query plus a Dictionary is the simplest and fastest way. If the table is large and only a subtree is needed, the database's recursive CTE (Common Table Expression) support or models such as the materialized path fit better; those are topics for the EF Core and SQL (Structured Query Language) series.

Common Pitfalls

Looking only at neighbours when validating a BST. A validator that compares each node only with its direct children accepts broken trees:

// wrong: only compares each node with its direct children
public static bool IsValidNaive(TreeNode<int>? node) =>
    node is null ||
    (node.Left is null || node.Left.Value < node.Value) &&
    (node.Right is null || node.Right.Value > node.Value) &&
    IsValidNaive(node.Left) && IsValidNaive(node.Right);

// right: every node must fit in the (min, max) window inherited from all its ancestors
public static bool IsValid(TreeNode<int>? node, long min = long.MinValue, long max = long.MaxValue) =>
    node is null ||
    node.Value > min && node.Value < max &&
    IsValid(node.Left, min, node.Value) &&
    IsValid(node.Right, node.Value, max);

[Fact]
public void NaiveValidator_AcceptsInvalidTree()
{
    // 50 -> left 30 -> right 60: 60 is in the LEFT subtree of 50, which is invalid
    TreeNode<int> root = new(50) { Left = new TreeNode<int>(30) { Right = new TreeNode<int>(60) }, Right = new TreeNode<int>(70) };

    Assert.True(BstValidator.IsValidNaive(root));
    Assert.False(BstValidator.IsValid(root));
}

Because 60 is larger than 30, it looks like it can sit to the right of 30, but since it is in the left subtree of 50 it must be smaller than 50. The correct validator carries a lower and upper bound from the ancestors down to each node. We keep the bounds as long so that int.MinValue and int.MaxValue are validated correctly too.

ParentId data with a cycle. A database foreign key does not prevent a cycle; the code that builds the tree has to check it itself, or a recursive menu renderer loops forever.

Running a recursive traversal on a degenerate tree. A tree that looks balanced on test data turns into a chain of depth n on production data imported in sorted order. Write every traversal whose depth depends on data iteratively, or limit the depth.

Forgetting to remove the successor in delete. If you copy the successor's value and do not remove it from the right subtree, the same value stays in the tree twice and Count is wrong. The random test against SortedSet catches this bug within the first few hundred steps.

A Small Experiment

★☆☆ Add Min(), Max() and Floor(T value) (the largest value less than or equal to value) to BinarySearchTree<T>. All are O(h); compare Floor with the upper bound from the series' binary search post.

★★☆ Write Remove iteratively: find the node to remove together with its parent, and solve the three cases by updating the parent's Left or Right. Run the random test against the new version too.

★★★ Write BuildBalanced(int[] sorted), which builds a balanced BST from a sorted array: the middle element is the root, the left and right halves are recursive subtrees. What is the height for 1,000,000 sorted IDs, and why is the recursion depth not a problem?

We have seen the degenerate tree problem; the fix is rebalancing the tree after every change. In the next post we look at AVL rotations, the rules of the red-black tree underneath .NET's SortedSet, and why database indexes are high-fanout B+trees rather than binary trees.