C# Binary Trees

A binary tree is a node-based data structure where each node can have at most two children, usually called the left child and the right child. Binary trees matter because many important algorithms use their shape to organize decisions, hierarchy, and search. In C#, you usually represent a tree with objects that reference other objects, then write traversal and search methods around those references.

Overview: How Binary Trees Work

A binary tree starts with a root node. From the root, every node may point to a left node, a right node, both, or neither. A node with no children is called a leaf. The depth of a node is the number of links from the root to that node, and the height of a tree is the number of levels in its longest root-to-leaf path.

In C#, a typical node is a class because nodes need reference identity. If two variables refer to the same node object, changing that node through one variable is visible through the other. The CLR allocates each node object on the managed heap. The node stores its value plus references for its child nodes. A missing child is represented with null, which is why nullable annotations such as Node? are useful in tree code.

A plain binary tree has no built-in ordering rule. It only says each node has up to two children. A binary search tree, often abbreviated BST, adds an ordering rule: values smaller than a node go in the left subtree, and values larger than a node go in the right subtree. With that rule, search can skip half of the remaining tree at each step when the tree is reasonably balanced.

The shape matters. A balanced binary search tree with n nodes has height around log n, so insert and search are usually fast. A badly unbalanced tree can become a linked list in disguise, where every node has only one child; then search degrades to O(n). The .NET base class library does not expose a general BinaryTree<T> type. It does provide sorted collections such as SortedSet<T> and SortedDictionary<TKey,TValue>, which use balanced tree-like structures internally so callers do not have to manage rotations and balancing.

Syntax

BinaryTreeNode<T> root = new BinaryTreeNode<T>(value);
root.Left = new BinaryTreeNode<T>(leftValue);
root.Right = new BinaryTreeNode<T>(rightValue);

Visit(root);        // pre-order, in-order, post-order, or level-order
Search(root, item); // often recursive for a binary search tree

Part	Meaning
BinaryTreeNode<T>	A common custom class name for a node that stores one value and child references.
Left and Right	References to child nodes, or null when that child does not exist.
root	The first node of the tree. An empty tree usually has a null root.
Traversal	A systematic way to visit every node: pre-order, in-order, post-order, or level-order.
BST search	Compare the target with the current node, then move left or right according to the ordering rule.

Examples

Building a Tree and Traversing It

using System;

class Program
{
    static void Main()
    {
        Node root = new Node("A");
        root.Left = new Node("B");
        root.Right = new Node("C");
        root.Left.Left = new Node("D");
        root.Left.Right = new Node("E");

        Console.WriteLine("Pre-order:");
        PrintPreOrder(root);

        Console.WriteLine("In-order:");
        PrintInOrder(root);

        Console.WriteLine("Post-order:");
        PrintPostOrder(root);
    }

    static void PrintPreOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        Console.WriteLine(node.Value);
        PrintPreOrder(node.Left);
        PrintPreOrder(node.Right);
    }

    static void PrintInOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        PrintInOrder(node.Left);
        Console.WriteLine(node.Value);
        PrintInOrder(node.Right);
    }

    static void PrintPostOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        PrintPostOrder(node.Left);
        PrintPostOrder(node.Right);
        Console.WriteLine(node.Value);
    }
}

class Node
{
    public Node(string value)
    {
        Value = value;
    }

    public string Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
}

Output:

Pre-order:
A
B
D
E
C
In-order:
D
B
E
A
C
Post-order:
D
E
B
C
A

This program builds a small tree by assigning Left and Right references. Pre-order visits the current node before its children, in-order visits left subtree, current node, then right subtree, and post-order visits children before the current node. The same nodes produce different output because traversal order is part of the algorithm.

A Binary Search Tree for Sorted Integers

using System;

class Program
{
    static void Main()
    {
        BinarySearchTree tree = new BinarySearchTree();
        int[] values = { 8, 3, 10, 1, 6, 14, 4, 7 };

        foreach (int value in values)
        {
            tree.Insert(value);
        }

        Console.WriteLine("Sorted values:");
        tree.PrintInOrder();

        Console.WriteLine($"Contains 6: {tree.Contains(6)}");
        Console.WriteLine($"Contains 13: {tree.Contains(13)}");
    }
}

class BinarySearchTree
{
    private Node? root;

    public void Insert(int value)
    {
        root = Insert(root, value);
    }

    private static Node Insert(Node? node, int value)
    {
        if (node == null)
        {
            return new Node(value);
        }

        if (value < node.Value)
        {
            node.Left = Insert(node.Left, value);
        }
        else if (value > node.Value)
        {
            node.Right = Insert(node.Right, value);
        }

        return node;
    }

    public bool Contains(int value)
    {
        Node? current = root;
        while (current != null)
        {
            if (value == current.Value)
            {
                return true;
            }

            current = value < current.Value ? current.Left : current.Right;
        }

        return false;
    }

    public void PrintInOrder()
    {
        PrintInOrder(root);
    }

    private static void PrintInOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        PrintInOrder(node.Left);
        Console.WriteLine(node.Value);
        PrintInOrder(node.Right);
    }

    private class Node
    {
        public Node(int value)
        {
            Value = value;
        }

        public int Value { get; }
        public Node? Left { get; set; }
        public Node? Right { get; set; }
    }
}

Output:

Sorted values:
1
3
4
6
7
8
10
14
Contains 6: True
Contains 13: False

The Insert method preserves the BST rule. Smaller values move left, larger values move right, and duplicates are ignored in this simple set-like version. In-order traversal of a valid BST prints values in sorted order because every left subtree is smaller than its parent and every right subtree is larger.

Level-Order Traversal and Tree Height

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Node root = new Node("CEO")
        {
            Left = new Node("Engineering")
            {
                Left = new Node("Platform"),
                Right = new Node("Product")
            },
            Right = new Node("Sales")
            {
                Left = new Node("Domestic"),
                Right = new Node("International")
            }
        };

        Console.WriteLine("Level order:");
        PrintLevelOrder(root);
        Console.WriteLine($"Height: {Height(root)}");
    }

    static void PrintLevelOrder(Node root)
    {
        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            Node current = queue.Dequeue();
            Console.WriteLine(current.Value);

            if (current.Left != null)
            {
                queue.Enqueue(current.Left);
            }

            if (current.Right != null)
            {
                queue.Enqueue(current.Right);
            }
        }
    }

    static int Height(Node? node)
    {
        if (node == null)
        {
            return 0;
        }

        return 1 + Math.Max(Height(node.Left), Height(node.Right));
    }
}

class Node
{
    public Node(string value)
    {
        Value = value;
    }

    public string Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
}

Output:

Level order:
CEO
Engineering
Sales
Platform
Product
Domestic
International
Height: 3

Level-order traversal uses a Queue<Node> to visit nodes breadth first. The root is processed first, then its children are enqueued, then their children, and so on. The height method is recursive: an empty subtree has height 0, and a non-empty subtree has height 1 plus the taller child subtree.

How It Works Step by Step

1. Create the root node. In memory, this is an object with a value and two child-reference fields.
2. Attach children by assigning references, such as root.Left = new Node(5). No values are copied into the parent; the parent stores a reference to another object.
3. For recursive traversal, each method call receives one node reference. If that reference is null, the method returns immediately.
4. Otherwise the method performs work before, between, or after recursive calls depending on the traversal type.
5. For BST search, compare the target with the current node. Equality succeeds, a smaller target moves to Left, and a larger target moves to Right.
6. Each recursive call uses the call stack. Very deep unbalanced trees can cause many nested calls, so iterative traversal with a stack or queue is sometimes safer.
7. When no live reference reaches a removed subtree, the garbage collector can reclaim those node objects later.

The most common traversal orders are worth memorizing. Pre-order is useful for copying or serializing a tree because the parent is seen first. In-order is especially important for binary search trees because it returns sorted data. Post-order is useful when children must be processed before the parent, such as deleting or evaluating expression trees. Level-order is useful when you care about distance from the root.

Common Mistakes

Forgetting the Null Base Case

static void PrintInOrder(Node node)
{
    PrintInOrder(node.Left);
    Console.WriteLine(node.Value);
    PrintInOrder(node.Right);
}

This recursive method never checks whether node is null. When it reaches a missing child, it tries to read node.Left and fails. The base case is not optional; it is what stops recursion at the edge of the tree.

using System;

class Program
{
    static void Main()
    {
        Node root = new Node(2) { Left = new Node(1), Right = new Node(3) };
        PrintInOrder(root);
    }

    static void PrintInOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        PrintInOrder(node.Left);
        Console.WriteLine(node.Value);
        PrintInOrder(node.Right);
    }
}

class Node
{
    public Node(int value)
    {
        Value = value;
    }

    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
}

Output:

1
2
3

Letting Duplicate Rules Happen by Accident

if (value <= node.Value)
{
    node.Left = Insert(node.Left, value);
}
else
{
    node.Right = Insert(node.Right, value);
}

This code sends duplicates into the left subtree. That may be correct if your tree is meant to store duplicates, but it should be a deliberate rule. A set-like BST should either ignore duplicates or store a count on the node.

using System;

class Program
{
    static void Main()
    {
        BinarySearchTree tree = new BinarySearchTree();
        tree.Insert(5);
        tree.Insert(5);
        tree.Insert(3);
        tree.Insert(7);
        tree.PrintInOrder();
    }
}

class BinarySearchTree
{
    private Node? root;

    public void Insert(int value)
    {
        root = Insert(root, value);
    }

    private static Node Insert(Node? node, int value)
    {
        if (node == null)
        {
            return new Node(value);
        }

        if (value < node.Value)
        {
            node.Left = Insert(node.Left, value);
        }
        else if (value > node.Value)
        {
            node.Right = Insert(node.Right, value);
        }

        return node;
    }

    public void PrintInOrder()
    {
        PrintInOrder(root);
    }

    private static void PrintInOrder(Node? node)
    {
        if (node == null)
        {
            return;
        }

        PrintInOrder(node.Left);
        Console.WriteLine(node.Value);
        PrintInOrder(node.Right);
    }

    private class Node
    {
        public Node(int value)
        {
            Value = value;
        }

        public int Value { get; }
        public Node? Left { get; set; }
        public Node? Right { get; set; }
    }
}

Output:

3
5
7

Best Practices

• Use Node? for child references so nullable warnings help you handle missing children.
• Write the empty-tree and empty-subtree cases first in recursive methods.
• Keep the BST ordering rule in one place, usually inside Insert, Contains, and any removal method.
• Define a clear duplicate policy: reject duplicates, count them, or store equal values consistently on one side.
• Prefer SortedSet<T> or SortedDictionary<TKey,TValue> for production sorted collections unless implementing trees is the goal.
• Remember that an unbalanced BST can become O(n); use a self-balancing structure when performance must be predictable.
• Use iterative traversal with Stack<T> or Queue<T> for very deep trees to avoid excessive recursion depth.

Practice Exercises

1. Create a binary tree of strings representing a small menu hierarchy, then print it in pre-order.
2. Add a Min method to the BST example. Hint: the minimum value is found by following Left until it is null.
3. Write a method that counts the leaf nodes in a tree. A leaf is a node whose Left and Right references are both null.

Summary

• A binary tree is made of nodes, and each node has at most two children.
• C# tree nodes are usually reference types with nullable Left and Right child references.
• Pre-order, in-order, post-order, and level-order traversals visit the same tree in different useful orders.
• A binary search tree adds an ordering rule, allowing search to move left or right instead of scanning every node.
• Balanced trees give better search behavior than unbalanced trees; built-in sorted collections handle balancing for production use.
• Recursive tree code must have a clear null base case.