Trees - potatoscript/dsa GitHub Wiki

In computer science, a tree is a hierarchical data structure. Just like your family tree 🏡 shows different generations, a tree in programming organizes data in a branching structure, with one root and multiple children. Each child can have their own children, and this goes on and on.

Here’s a basic tree structure:

         Root (Grandparent)
        /         \
   Child 1       Child 2
     /  \         /     \
  Grandchild 1  Grandchild 2 Grandchild 3

• Root is the starting point (like the grandparent in a family tree).
• Child 1, Child 2 are like the children of the root (grandparent).
• Grandchild 1, Grandchild 2, Grandchild 3 are the grandchildren (children of the child nodes).

• Root: The topmost node in a tree. It’s the starting point.
• Node: Each data point in the tree. Nodes are connected by edges.
• Edge: The line connecting two nodes. It represents the relationship between them.
• Leaf: A node that has no children, like the leaves of a tree 🌿.
• Parent: A node that has children (like a parent in a family).
• Child: A node that is a descendant of another node.
• Sibling: Nodes that share the same parent (like brothers and sisters).

Let’s compare it to something we all know: a family tree! 🌳

Imagine a family with generations of family members. The root would be your grandparent (the top of the tree), and the children are their sons or daughters (your parents and aunts/uncles). The grandchildren would be your generation, and so on.

In programming, trees are used to store data in a way that makes it easy to add, search, and delete information!

Here’s how we can represent a tree in C#:

Each node in a tree has a value and links to its children.

class TreeNode
{
    public string Value;
    public List<TreeNode> Children;

    public TreeNode(string value)
    {
        Value = value;
        Children = new List<TreeNode>();
    }
}

Let’s build a simple tree with a root and two children:

class Program
{
    static void Main()
    {
        // Root of the tree
        TreeNode root = new TreeNode("Grandparent");

        // Children of the root
        TreeNode child1 = new TreeNode("Parent 1");
        TreeNode child2 = new TreeNode("Parent 2");

        // Adding children to root
        root.Children.Add(child1);
        root.Children.Add(child2);

        // Grandchildren
        TreeNode grandchild1 = new TreeNode("Child 1");
        TreeNode grandchild2 = new TreeNode("Child 2");

        // Adding grandchildren to Parent 1
        child1.Children.Add(grandchild1);
        child1.Children.Add(grandchild2);

        // Printing tree structure
        Console.WriteLine(root.Value); // Grandparent
        foreach (var child in root.Children)
        {
            Console.WriteLine($"  {child.Value}"); // Parent 1, Parent 2
            foreach (var grandchild in child.Children)
            {
                Console.WriteLine($"    {grandchild.Value}"); // Child 1, Child 2
            }
        }
    }
}

Grandparent
  Parent 1
    Child 1
    Child 2
  Parent 2

There are different types of trees depending on how the data is organized:

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

Example:

        1
       / \
      2   3
     / \
    4   5

In a Binary Search Tree, for any given node:

• All values in the left subtree are less than the node’s value.
• All values in the right subtree are greater than the node’s value.

Example:

        10
       /  \
      5   15
     / \    \
    3   7    20

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

A heap is a special type of binary tree that satisfies the heap property:

• Max-heap: The value of each node is greater than or equal to the values of its children.
• Min-heap: The value of each node is less than or equal to the values of its children.

• Insertion: Add a node to the tree.
  Example: Add a new child to a parent.

• Traversal: Visit all the nodes in the tree. There are three common ways to do this:

  • Pre-order: Visit the root first, then left, then right.
  • In-order: Visit the left child first, then the root, then right.
  • Post-order: Visit the left and right children first, then the root.

• Searching: Find a specific node in the tree. Example: Find the child node with a particular name.

void PreOrder(TreeNode node)
{
    if (node == null)
        return;
    Console.WriteLine(node.Value);
    foreach (var child in node.Children)
    {
        PreOrder(child);
    }
}

void InOrder(TreeNode node)
{
    if (node == null)
        return;
    InOrder(node.Left);
    Console.WriteLine(node.Value);
    InOrder(node.Right);
}

void PostOrder(TreeNode node)
{
    if (node == null)
        return;
    foreach (var child in node.Children)
    {
        PostOrder(child);
    }
    Console.WriteLine(node.Value);
}

• File Systems: The structure of files and directories is often represented using trees.
• Web Crawlers: Crawlers use trees to explore and index websites.
• Decision Trees: Used in machine learning to make decisions.
• Game Trees: Represent possible moves in games (like chess).
• Expression Parsing: Trees are used to parse and evaluate mathematical expressions.

• Unbalanced Trees: If a tree becomes unbalanced (e.g., adding nodes in a sorted order), it can degrade into a linked list, leading to slower operations.
• Memory Usage: Trees can use more memory due to pointers/edges between nodes.

• Search: O(log n) for balanced trees, but O(n) for unbalanced trees.
• Insertion: O(log n) for balanced trees, but O(n) for unbalanced trees.
• Deletion: O(log n) for balanced trees, but O(n) for unbalanced trees.
• Traversal: O(n) – Visit every node once.

✅ Trees organize data in a hierarchical structure, making it easy to search, add, and delete data.
✅ Binary Trees have two children per node.
✅ Binary Search Trees store data in a sorted way.
✅ Tree Operations like insert, search, and traversal are crucial.
✅ Big O for trees is O(log n) for balanced trees, and O(n) for unbalanced trees.