Understanding Trees in C#: Binary Trees, BSTs, and Traversal Algorithms

Trees are one of the most important data structures in computer science. They are hierarchical, non-linear structures that model relationships and enable efficient searching, sorting, and organizing of data. In this post, we’ll explore how trees work, what makes Binary Trees and Binary Search Trees special, and how to implement and traverse them in C#.

What Is a Tree?

A tree is a hierarchical data structure made up of nodes. Each node contains data and references to its children. The topmost node is the root, and nodes with no children are called leaves.

Key Terminology:

Root: The first node in the tree
Parent and Child: Relationships between nodes
Leaf: A node with no children
Depth: Distance from root to a node
Height: Longest path from a node to a leaf

Binary Trees and Binary Search Trees (BST)

Binary Tree

A binary tree is a tree where each node can have at most two children: left and right.

Binary Search Tree (BST)

A BST is a binary tree with an ordering property:

Left subtree contains values less than the parent
Right subtree contains values greater than the parent

This makes searching, insertion, and deletion operations more efficient (average-case O(log n)).

C# Tree Node Implementation

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

BST Insert & Search Implementation

public class BinarySearchTree
{
    public TreeNode Root;

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

    private TreeNode InsertRecursive(TreeNode node, int value)
    {
        if (node == null) return new TreeNode(value);

        if (value < node.Value)
            node.Left = InsertRecursive(node.Left, value);
        else if (value > node.Value)
            node.Right = InsertRecursive(node.Right, value);

        return node;
    }

    public bool Search(int value)
    {
        return SearchRecursive(Root, value);
    }

    private bool SearchRecursive(TreeNode node, int value)
    {
        if (node == null) return false;
        if (node.Value == value) return true;

        return value < node.Value
            ? SearchRecursive(node.Left, value)
            : SearchRecursive(node.Right, value);
    }
}

Tree Traversal Algorithms

Traversal means visiting every node in a specific order.

Inorder (Left, Root, Right)

void Inorder(TreeNode node)
{
    if (node == null) return;
    Inorder(node.Left);
    Console.Write(node.Value + " ");
    Inorder(node.Right);
}

Preorder (Root, Left, Right)

void Preorder(TreeNode node)
{
    if (node == null) return;
    Console.Write(node.Value + " ");
    Preorder(node.Left);
    Preorder(node.Right);
}

Postorder (Left, Right, Root)

void Postorder(TreeNode node)
{
    if (node == null) return;
    Postorder(node.Left);
    Postorder(node.Right);
    Console.Write(node.Value + " ");
}

Level-order (BFS using Queue)

void LevelOrder(TreeNode root)
{
    if (root == null) return;
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        TreeNode node = queue.Dequeue();
        Console.Write(node.Value + " ");
        if (node.Left != null) queue.Enqueue(node.Left);
        if (node.Right != null) queue.Enqueue(node.Right);
    }
}

Real-World Applications of Trees

File system hierarchies
Auto-suggestion (prefix trees)
Decision trees in AI
Expression parsing in compilers
Database indexing (B-Trees)

Practice Problems

Print all leaf nodes of a binary tree
Find the height of a tree
Validate if a binary tree is a BST
Mirror (invert) a binary tree
Find the lowest common ancestor of two nodes