6.6 - Trees

Trees are hierarchical data structures that consist of nodes connected by edges. Unlike linear data structures such as arrays and linked lists, trees have a hierarchical relationship between elements. This section explores various types of trees, their implementations, operations, and applications in C#.

6.6.1 - Tree Terminology

Before diving into specific tree types, let's understand some common terminology:

• Node: A basic unit of a tree that contains data and references to its children.
• Root: The topmost node of a tree, which has no parent.
• Parent: A node that has one or more child nodes.
• Child: A node that has a parent node.
• Leaf: A node that has no children.
• Internal Node: A node that has at least one child.
• Sibling: Nodes that share the same parent.
• Ancestor: A node reachable by repeated proceeding from child to parent.
• Descendant: A node reachable by repeated proceeding from parent to child.
• Subtree: A tree consisting of a node and all its descendants.
• Depth: The length of the path from the root to a node.
• Height: The length of the longest path from a node to a leaf.
• Level: The set of nodes at the same depth.
• Degree: The number of children of a node.
• Edge: The connection between two nodes.

6.6.2 - Binary Trees and Binary Search Trees

There are various types of trees, each with its own characteristics and use cases:

6.6.2.1 - Binary Tree

A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child.

    A
   / \
  B   C
 / \   \
D   E   F

6.6.2.2 - Binary Search Tree (BST)

A binary search tree is a binary tree in which the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

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

6.6.2.3 - AVL Tree

An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one.

6.6.2.4 - Red-Black Tree

A red-black tree is a self-balancing binary search tree with an extra bit of data per node, its color (red or black), which is used to ensure that the tree remains balanced during insertions and deletions.

6.6.2.5 - B-Tree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is commonly used in databases and file systems.

6.6.2.6 - Trie (Prefix Tree)

A trie is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It is particularly useful for searching for keys with a common prefix.

6.6.3 - Tree Traversal Algorithms

Let's implement a basic binary tree in C#:

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

    public BinaryTreeNode(T value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class BinaryTree<T>
{
    public BinaryTreeNode<T> Root { get; private set; }

    public BinaryTree()
    {
        Root = null;
    }

    public BinaryTree(T rootValue)
    {
        Root = new BinaryTreeNode<T>(rootValue);
    }

    // Other methods will be added later
}

Tree traversal is the process of visiting each node in a tree exactly once. There are several traversal algorithms:

Depth-first traversal explores as far as possible along each branch before backtracking.

6.6.3.1 - Preorder Traversal (Root-Left-Right)

public void PreorderTraversal(BinaryTreeNode<T> node, Action<T> action)
{
    if (node == null)
        return;

    action(node.Value); // Process the root
    PreorderTraversal(node.Left, action); // Process the left subtree
    PreorderTraversal(node.Right, action); // Process the right subtree
}

6.6.3.2 - Inorder Traversal (Left-Root-Right)

public void InorderTraversal(BinaryTreeNode<T> node, Action<T> action)
{
    if (node == null)
        return;

    InorderTraversal(node.Left, action); // Process the left subtree
    action(node.Value); // Process the root
    InorderTraversal(node.Right, action); // Process the right subtree
}

6.6.3.3 - Postorder Traversal (Left-Right-Root)

public void PostorderTraversal(BinaryTreeNode<T> node, Action<T> action)
{
    if (node == null)
        return;

    PostorderTraversal(node.Left, action); // Process the left subtree
    PostorderTraversal(node.Right, action); // Process the right subtree
    action(node.Value); // Process the root
}

6.6.3.4 - Breadth-First Traversal (Level Order Traversal)

Breadth-first traversal explores all nodes at the present depth before moving on to nodes at the next depth level.

public void LevelOrderTraversal(BinaryTreeNode<T> root, Action<T> action)
{
    if (root == null)
        return;

    Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        BinaryTreeNode<T> node = queue.Dequeue();
        action(node.Value);

        if (node.Left != null)
            queue.Enqueue(node.Left);

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

6.6.4 - Balanced Trees (AVL, Red-Black)

A binary search tree is a binary tree with the property that the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

6.6.4.1 - BST Implementation

public class BinarySearchTree<T> where T : IComparable<T>
{
    private class Node
    {
        public T Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public Node(T value)
        {
            Value = value;
            Left = null;
            Right = null;
        }
    }

    private Node root;

    public BinarySearchTree()
    {
        root = null;
    }

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

    private Node InsertRecursive(Node node, T value)
    {
        if (node == null)
            return new Node(value);

        int compareResult = value.CompareTo(node.Value);

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

        return node;
    }

    public bool Contains(T value)
    {
        return ContainsRecursive(root, value);
    }

    private bool ContainsRecursive(Node node, T value)
    {
        if (node == null)
            return false;

        int compareResult = value.CompareTo(node.Value);

        if (compareResult == 0)
            return true;
        else if (compareResult < 0)
            return ContainsRecursive(node.Left, value);
        else
            return ContainsRecursive(node.Right, value);
    }

    public void Remove(T value)
    {
        root = RemoveRecursive(root, value);
    }

    private Node RemoveRecursive(Node node, T value)
    {
        if (node == null)
            return null;

        int compareResult = value.CompareTo(node.Value);

        if (compareResult < 0)
            node.Left = RemoveRecursive(node.Left, value);
        else if (compareResult > 0)
            node.Right = RemoveRecursive(node.Right, value);
        else
        {
            // Node with only one child or no child
            if (node.Left == null)
                return node.Right;
            else if (node.Right == null)
                return node.Left;

            // Node with two children: Get the inorder successor (smallest in the right subtree)
            node.Value = FindMinValue(node.Right);

            // Delete the inorder successor
            node.Right = RemoveRecursive(node.Right, node.Value);
        }

        return node;
    }

    private T FindMinValue(Node node)
    {
        T minValue = node.Value;
        while (node.Left != null)
        {
            minValue = node.Left.Value;
            node = node.Left;
        }
        return minValue;
    }

    public void InorderTraversal(Action<T> action)
    {
        InorderTraversalRecursive(root, action);
    }

    private void InorderTraversalRecursive(Node node, Action<T> action)
    {
        if (node == null)
            return;

        InorderTraversalRecursive(node.Left, action);
        action(node.Value);
        InorderTraversalRecursive(node.Right, action);
    }
}

6.6.4.2 - BST Operations

The primary operations of a binary search tree are:

1. Insertion: Add a new node to the tree while maintaining the BST property.
2. Deletion: Remove a node from the tree while maintaining the BST property.
3. Search: Find a node with a specific value.
4. Traversal: Visit all nodes in a specific order.

6.6.4.3 - BST Performance

The performance of a binary search tree depends on its shape:

• Best Case: A balanced tree with a height of log(n), where n is the number of nodes.
• Worst Case: A degenerate tree (essentially a linked list) with a height of n.

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)

6.6.5 - Self-Balancing Trees

Self-balancing trees are binary search trees that automatically keep their height small in the face of arbitrary insertions and deletions.

6.6.5.1 - AVL Tree

An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.

AVL Tree Implementation:

public class AVLTree<T> where T : IComparable<T>
{
    private class Node
    {
        public T Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public int Height { get; set; }

        public Node(T value)
        {
            Value = value;
            Left = null;
            Right = null;
            Height = 1; // New node is initially added at leaf
        }
    }

    private Node root;

    public AVLTree()
    {
        root = null;
    }

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

    private Node InsertRecursive(Node node, T value)
    {
        if (node == null)
            return new Node(value);

        int compareResult = value.CompareTo(node.Value);

        if (compareResult < 0)
            node.Left = InsertRecursive(node.Left, value);
        else if (compareResult > 0)
            node.Right = InsertRecursive(node.Right, value);
        else
            return node; // Duplicate values not allowed

        // Update height of this ancestor node
        node.Height = 1 + Math.Max(GetHeight(node.Left), GetHeight(node.Right));

        // Get the balance factor of this ancestor node to check whether this node became unbalanced
        int balance = GetBalance(node);

        // If this node becomes unbalanced, then there are 4 cases

        // Left Left Case
        if (balance > 1 && value.CompareTo(node.Left.Value) < 0)
            return RightRotate(node);

        // Right Right Case
        if (balance < -1 && value.CompareTo(node.Right.Value) > 0)
            return LeftRotate(node);

        // Left Right Case
        if (balance > 1 && value.CompareTo(node.Left.Value) > 0)
        {
            node.Left = LeftRotate(node.Left);
            return RightRotate(node);
        }

        // Right Left Case
        if (balance < -1 && value.CompareTo(node.Right.Value) < 0)
        {
            node.Right = RightRotate(node.Right);
            return LeftRotate(node);
        }

        return node;
    }

    private int GetHeight(Node node)
    {
        if (node == null)
            return 0;
        return node.Height;
    }

    private int GetBalance(Node node)
    {
        if (node == null)
            return 0;
        return GetHeight(node.Left) - GetHeight(node.Right);
    }

    private Node RightRotate(Node y)
    {
        Node x = y.Left;
        Node T2 = x.Right;

        // Perform rotation
        x.Right = y;
        y.Left = T2;

        // Update heights
        y.Height = Math.Max(GetHeight(y.Left), GetHeight(y.Right)) + 1;
        x.Height = Math.Max(GetHeight(x.Left), GetHeight(x.Right)) + 1;

        // Return new root
        return x;
    }

    private Node LeftRotate(Node x)
    {
        Node y = x.Right;
        Node T2 = y.Left;

        // Perform rotation
        y.Left = x;
        x.Right = T2;

        // Update heights
        x.Height = Math.Max(GetHeight(x.Left), GetHeight(x.Right)) + 1;
        y.Height = Math.Max(GetHeight(y.Left), GetHeight(y.Right)) + 1;

        // Return new root
        return y;
    }

    public bool Contains(T value)
    {
        return ContainsRecursive(root, value);
    }

    private bool ContainsRecursive(Node node, T value)
    {
        if (node == null)
            return false;

        int compareResult = value.CompareTo(node.Value);

        if (compareResult == 0)
            return true;
        else if (compareResult < 0)
            return ContainsRecursive(node.Left, value);
        else
            return ContainsRecursive(node.Right, value);
    }

    public void InorderTraversal(Action<T> action)
    {
        InorderTraversalRecursive(root, action);
    }

    private void InorderTraversalRecursive(Node node, Action<T> action)
    {
        if (node == null)
            return;

        InorderTraversalRecursive(node.Left, action);
        action(node.Value);
        InorderTraversalRecursive(node.Right, action);
    }
}

6.6.5.2 - Red-Black Tree

A red-black tree is a self-balancing binary search tree with an extra bit of data per node, its color (red or black), which is used to ensure that the tree remains balanced during insertions and deletions.

C# provides a built-in implementation of a red-black tree through the SortedSet<T> and SortedDictionary<TKey, TValue> classes.

// Creating a sorted set (red-black tree)
SortedSet<int> sortedSet = new SortedSet<int>();

// Adding elements
sortedSet.Add(5);
sortedSet.Add(3);
sortedSet.Add(7);
sortedSet.Add(1);
sortedSet.Add(9);

// Checking if an element exists
bool contains = sortedSet.Contains(3);

// Removing an element
sortedSet.Remove(3);

// Iterating through the sorted set (elements will be in ascending order)
foreach (int value in sortedSet)
{
    Console.WriteLine(value);
}

6.6.6 - B-Tree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is commonly used in databases and file systems.

While C# doesn't provide a built-in B-tree implementation, you can implement one yourself or use third-party libraries.

6.6.7 - Trie (Prefix Tree)

A trie is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It is particularly useful for searching for keys with a common prefix.

6.6.7.1 - Trie Implementation

public class Trie
{
    private class TrieNode
    {
        public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
        public bool IsEndOfWord { get; set; }
    }

    private TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode current = root;

        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                current.Children[c] = new TrieNode();

            current = current.Children[c];
        }

        current.IsEndOfWord = true;
    }

    public bool Search(string word)
    {
        TrieNode node = FindNode(word);
        return node != null && node.IsEndOfWord;
    }

    public bool StartsWith(string prefix)
    {
        return FindNode(prefix) != null;
    }

    private TrieNode FindNode(string word)
    {
        TrieNode current = root;

        foreach (char c in word)
        {
            if (!current.Children.ContainsKey(c))
                return null;

            current = current.Children[c];
        }

        return current;
    }
}

6.6.7.2 - Trie Applications

Tries are used in various applications:

1. Autocomplete: Suggesting words as a user types.
2. Spell Checking: Checking if a word is spelled correctly.
3. IP Routing: Finding the next hop in a routing table.
4. Longest Prefix Matching: Finding the longest matching prefix in a set of strings.

6.6.8 - Tree Applications

Trees are used in various applications:

1. File Systems: Directories and files are organized in a tree structure.
2. Database Indexing: B-trees and B+ trees are used to index databases.
3. Expression Evaluation: Expression trees are used to evaluate arithmetic expressions.
4. Network Routing: Routing tables are often implemented as trees.
5. Compiler Design: Abstract syntax trees are used to represent the structure of a program.
6. AI and Machine Learning: Decision trees are used for classification and regression.

6.6.9 - Tree Algorithms

Here are some common algorithms used with trees:

6.6.9.1 - Finding the Height of a Tree

public int GetHeight(BinaryTreeNode<T> node)
{
    if (node == null)
        return 0;

    int leftHeight = GetHeight(node.Left);
    int rightHeight = GetHeight(node.Right);

    return Math.Max(leftHeight, rightHeight) + 1;
}

6.6.9.2 - Counting Nodes

public int CountNodes(BinaryTreeNode<T> node)
{
    if (node == null)
        return 0;

    return 1 + CountNodes(node.Left) + CountNodes(node.Right);
}

6.6.9.3 - Checking if a Binary Tree is a Binary Search Tree

public bool IsBST(BinaryTreeNode<T> node, T minValue, T maxValue) where T : IComparable<T>
{
    if (node == null)
        return true;

    if (node.Value.CompareTo(minValue) < 0 || node.Value.CompareTo(maxValue) > 0)
        return false;

    return IsBST(node.Left, minValue, node.Value) && IsBST(node.Right, node.Value, maxValue);
}

6.6.9.4 - Finding the Lowest Common Ancestor (LCA)

public BinaryTreeNode<T> FindLCA(BinaryTreeNode<T> node, BinaryTreeNode<T> p, BinaryTreeNode<T> q)
{
    if (node == null)
        return null;

    if (node == p || node == q)
        return node;

    BinaryTreeNode<T> leftLCA = FindLCA(node.Left, p, q);
    BinaryTreeNode<T> rightLCA = FindLCA(node.Right, p, q);

    if (leftLCA != null && rightLCA != null)
        return node;

    return leftLCA != null ? leftLCA : rightLCA;
}

6.60 - Performance Considerations

When working with trees, consider the following performance aspects:

1. Tree Balance: The balance of a tree affects its performance. A balanced tree has better performance than an unbalanced tree.
2. Tree Height: The height of a tree affects the time complexity of operations. A shorter tree has better performance.
3. Node Structure: The structure of a node affects memory usage and cache locality.
4. Traversal Method: The choice of traversal method affects the order in which nodes are visited and the performance of the traversal.

6.60 - Best Practices

Here are some best practices for working with trees in C#:

1. Choose the Right Tree Type: Use the appropriate tree type for your specific requirements.
2. Balance Trees: Use self-balancing trees when the order of insertions and deletions is unpredictable.
3. Use Built-in Collections When Possible: Use built-in collections like SortedSet<T> and SortedDictionary<TKey, TValue> when appropriate.
4. Implement Custom Trees When Needed: Implement custom trees when you need specific behavior not provided by built-in collections.
5. Be Mindful of Memory Usage: Trees can use a significant amount of memory, especially with many nodes.
6. Consider Thread Safety: Ensure thread safety when working with trees in multi-threaded applications.

---

In the next section, we'll explore graphs, which are more general data structures that can represent complex relationships between objects.