What are trees, binary trees and binary search trees? Explain traversals, why balance matters, and where trees appear in real .NET systems and databases.

1. Why balance matters, and how it is kept

Insert 10, 20, 30, 40, 50 into a plain BST:

[10]
   \
   [20]
      \
      [30]          height = n - 1 → every operation O(n)
         \
         [40]
            \
            [50]

Self-balancing trees fix this with rotations, which re-hang nodes in O(1) while keeping the BST order:

Left rotation at 10 (right-heavy):

  [10]                 [20]
     \                /    \
     [20]    ──►   [10]    [30]
        \
        [30]

2. B+ tree shape

                     [ 100 | 500 | 900 ]                  root page
             /            |           |          \
   [10|40|70]       [200|300|400]  [600|700|800]  [950|...]  intermediate pages
      ...                ...            ...           ...
   leaf pages hold keys + row locators, linked left↔right for range scans

Leaves are linked, so WHERE OrderDate BETWEEN ... seeks once then scans sideways. This is why index key order and "sargable" predicates matter.

3. Traversal costs

4. Trees in .NET

• Roslyn syntax trees (SyntaxTree, SyntaxNode) for analysers and source generators.
• Expression trees (Expression<Func<T, bool>>) that EF Core walks and translates to SQL.
• JSON and XML (JsonNode, JsonDocument, XDocument), and the HTML DOM.
• Configuration hierarchies (IConfiguration sections); DI registrations form a dependency graph (a DAG rather than a tree).
• SQL Server hierarchyid and adjacency-list tables (ParentId) for org charts and categories, loaded with recursive CTEs.

5. Recursion versus iteration

Recursive traversals are elegant, but call depth equals tree height. For degenerate or user-supplied trees, use an explicit stack (DFS) or queue (BFS) to avoid StackOverflowException, which cannot be caught.

6. Classic interview problems

• Max depth, check balanced, validate a BST (track min/max bounds, not just the parent).
• Lowest common ancestor.
• Serialise and deserialise a tree.
• Level-order traversal, zigzag order.
• Build a tree from parent pointers in O(n) with a dictionary.

7. Try it yourself

1. Insert 1–10,000 in order into a simple BST and measure height; then insert shuffled values.
2. Compare with SortedSet<int> timings.
3. In SQL Server, run SET STATISTICS IO ON and query by an indexed column; note logical reads (about the index depth).
4. Write in-order, pre-order and post-order traversals and print the results for a small tree.

public sealed class Node(int value)
{
    public int Value { get; } = value;
    public Node? Left { get; set; }
    public Node? Right { get; set; }
}

// BST insert and search: O(height)
public static Node Insert(Node? root, int value)
{
    if (root is null) return new Node(value);
    if (value < root.Value) root.Left = Insert(root.Left, value);
    else if (value > root.Value) root.Right = Insert(root.Right, value);
    return root;
}

public static bool Contains(Node? node, int value)
{
    while (node is not null)
    {
        if (value == node.Value) return true;
        node = value < node.Value ? node.Left : node.Right;
    }
    return false;
}

// Validate a BST with bounds (checking only parent/child is a classic bug)
public static bool IsValidBst(Node? node, long min = long.MinValue, long max = long.MaxValue) =>
    node is null ||
    (node.Value > min && node.Value < max &&
     IsValidBst(node.Left, min, node.Value) &&
     IsValidBst(node.Right, node.Value, max));

// In-order traversal without recursion
public static IEnumerable<int> InOrder(Node? root)
{
    var stack = new Stack<Node>();
    var current = root;
    while (current is not null || stack.Count > 0)
    {
        while (current is not null) { stack.Push(current); current = current.Left; }
        current = stack.Pop();
        yield return current.Value;
        current = current.Right;
    }
}

// Build a category tree from flat rows in O(n)
public sealed record CategoryRow(int Id, int? ParentId, string Name);
public sealed class Category(int id, string name)
{
    public int Id { get; } = id;
    public string Name { get; } = name;
    public List<Category> Children { get; } = [];
}

public static List<Category> BuildTree(IReadOnlyList<CategoryRow> rows)
{
    var byId = rows.ToDictionary(r => r.Id, r => new Category(r.Id, r.Name));
    var roots = new List<Category>();
    foreach (var row in rows)
    {
        if (row.ParentId is int parentId) byId[parentId].Children.Add(byId[row.Id]);
        else roots.Add(byId[row.Id]);
    }
    return roots;
}