Trees and binary trees

Arrays, lists, stacks and queues are linear: every item has at most one item before it and one after it. Much real data is not like that. A project has buildings, a building has levels, a level has columns. A folder has files and sub-folders. A web page has elements inside elements. This shape, one thing branching into several, is a tree.

The vocabulary

Two facts hold for every tree: every node except the root has exactly one parent, and there are no loops. So a tree with n nodes always has n − 1 edges. If any node had two parents, or you could walk in a circle, it would be a graph (covered in the Graphs module).

A general tree in C#

A node stores its data and a list of children. Because each child is itself the root of a smaller tree, almost every tree algorithm is naturally recursive: handle this node, then call yourself on each child.

1var project = new TreeNode("Project");2var a = project.Add("Building A");3var a1 = a.Add("Level 1");4a1.Add("C1");5a1.Add("C2");6a.Add("Level 2").Add("C3");7project.Add("Building B").Add("Level 1").Add("B1");8 9Print(project, 0);10Console.WriteLine($"Nodes: {Count(project)}, height: {Height(project)}");11 12static void Print(TreeNode node, int depth)13{14    Console.WriteLine(new string(' ', depth * 2) + node.Name);   // indent by depth15    foreach (var child in node.Children)16        Print(child, depth + 1);17}18 19static int Count(TreeNode node) => 1 + node.Children.Sum(c => Count(c));20 21static int Height(TreeNode node) =>22    node.Children.Count == 0 ? 0 : 1 + node.Children.Max(c => Height(c));23 24class TreeNode25{26    public string Name { get; }27    public List<TreeNode> Children { get; } = new();28    public TreeNode(string name) => Name = name;29 30    public TreeNode Add(string name)31    {32        var child = new TreeNode(name);33        Children.Add(child);34        return child;                       // so calls can be chained35    }36}

Project
  Building A
    Level 1
      C1
      C2
    Level 2
      C3
  Building B
    Level 1
      B1
Nodes: 10, height: 3

You use trees like this every day: System.IO.Directory (folders), XML and JSON documents (XElement, JsonNode), the HTML DOM, menus, an organisation chart, and Revit or Tekla model hierarchies.

Binary trees

In a binary tree every node has at most two children, called left and right. The order matters: a node with only a left child is different from one with only a right child. Binary trees are the base of binary search trees, heaps and expression trees in the next lessons.

1//        82//      /   \3//     4     124//    / \5//   2   66var root = new Node(8,7    new Node(4, new Node(2), new Node(6)),8    new Node(12));9 10Console.WriteLine(root.Left!.Right!.Value);   // 8 → left → right11 12record Node(int Value, Node? Left = null, Node? Right = null);

6

Why height is the number to watch

Most tree operations walk from the root down one path, so they cost O(height). How tall a binary tree with n nodes is depends entirely on its shape:

• Perfect / complete (every level full, or full except the last, filled from the left): height ≈ log₂ n. A million nodes fit in about 20 levels.
• Degenerate (every node has one child): it is really a linked list, height n − 1. Walking it is O(n).

Keeping trees short (“balanced”) is what makes them fast. The whole Trees module is about that idea.

1var project = new TreeNode("Project");2var a = project.Add("Building A");3var a1 = a.Add("Level 1");4a1.Add("C1");5a1.Add("C2");6a.Add("Level 2").Add("C3");7project.Add("Building B").Add("Level 1").Add("B1");8 9Console.WriteLine(Leaves(project));10Console.WriteLine(Find(project, "C3")?.Name ?? "not found");11Console.WriteLine(Find(project, "C9")?.Name ?? "not found");12 13static int Leaves(TreeNode node) =>14    node.Children.Count == 0 ? 1 : node.Children.Sum(c => Leaves(c));15 16static TreeNode? Find(TreeNode node, string name)17{18    if (node.Name == name) return node;19    foreach (var child in node.Children)20    {21        var hit = Find(child, name);22        if (hit is not null) return hit;23    }24    return null;25}26 27class TreeNode28{29    public string Name { get; }30    public List<TreeNode> Children { get; } = new();31    public TreeNode(string name) => Name = name;32    public TreeNode Add(string name) { var c = new TreeNode(name); Children.Add(c); return c; }33}

4
C3
not found