Trees & Binary Trees

A tree is a hierarchical data structure with a root node and child nodes forming a branching structure. Trees are everywhere — file systems, HTML DOM, org charts.

Terminology

• Root — the top node (no parent)
• Leaf — a node with no children
• Depth — distance from root to a node
• Height — distance from a node to its deepest leaf
• Subtree — a node and all its descendants

Binary Tree

A binary tree is a tree where each node has at most two children (left and right).

public class TreeNode<T>
{
    public T Value { get; set; }
    public TreeNode<T>? Left { get; set; }
    public TreeNode<T>? Right { get; set; }

    public TreeNode(T value)
    {
        Value = value;
    }
}

Traversal Orders

// In-Order (Left, Root, Right) — gives sorted order for BST
public static void InOrder(TreeNode<int>? node)
{
    if (node == null) return;
    InOrder(node.Left);
    Console.Write($"{node.Value} ");
    InOrder(node.Right);
}

// Pre-Order (Root, Left, Right) — useful for copying trees
public static void PreOrder(TreeNode<int>? node)
{
    if (node == null) return;
    Console.Write($"{node.Value} ");
    PreOrder(node.Left);
    PreOrder(node.Right);
}

// Post-Order (Left, Right, Root) — useful for deletion
public static void PostOrder(TreeNode<int>? node)
{
    if (node == null) return;
    PostOrder(node.Left);
    PostOrder(node.Right);
    Console.Write($"{node.Value} ");
}

Example

//       4
//      / \
//     2    6
//    / \  / \
//   1   3 5   7

var root = new TreeNode<int>(4);
root.Left = new TreeNode<int>(2);
root.Right = new TreeNode<int>(6);
root.Left.Left = new TreeNode<int>(1);
root.Left.Right = new TreeNode<int>(3);
root.Right.Left = new TreeNode<int>(5);
root.Right.Right = new TreeNode<int>(7);

InOrder(root); // 1 2 3 4 5 6 7