Trees, binary search trees and traversals — Data Structures & Algorithms

5. Trees, binary search trees and traversals

Intermediate★ Must knowLesson 5 of 10

A tree is nodes connected parent → children with no cycles. A binary search tree (BST) keeps left < node < right, so search, insert and delete are O(height): O(log n) when balanced, O(n) when it degenerates into a line (inserting sorted data).

csharp

public class TreeNode(int val) { public int Val = val; public TreeNode? Left, Right; }

bool Contains(TreeNode? n, int x) =>
    n != null && (x == n.Val || (x < n.Val ? Contains(n.Left, x) : Contains(n.Right, x)));

void InOrder(TreeNode? n, List<int> output)   // left, node, right → sorted order for a BST
{
    if (n == null) return;
    InOrder(n.Left, output); output.Add(n.Val); InOrder(n.Right, output);
}

int Height(TreeNode? n) => n == null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));

List<List<int>> LevelOrder(TreeNode? root)    // BFS with a queue
{
    var result = new List<List<int>>();
    if (root == null) return result;
    var q = new Queue<TreeNode>([root]);
    while (q.Count > 0)
    {
        var level = new List<int>();
        for (int size = q.Count; size > 0; size--)
        {
            var n = q.Dequeue();
            level.Add(n.Val);
            if (n.Left != null) q.Enqueue(n.Left);
            if (n.Right != null) q.Enqueue(n.Right);
        }
        result.Add(level);
    }
    return result;
}

Traversals: pre-order (node, left, right — copy a tree), in-order (sorted output), post-order (children first — delete a tree, evaluate expressions), level-order/BFS.

Balanced trees keep height O(log n) automatically: AVL, red-black (.NET SortedDictionary/SortedSet), and B-trees/B+ trees — very wide trees (hundreds of keys per node) designed for disks. SQL Server indexes are B+ trees: an index seek on a table of 10 million rows touches only 3–4 pages (root → intermediate → leaf).