Understanding Trees

What Is a Tree?

A tree is a hierarchical data structure that represents data as parent–child relationships. Unlike arrays, linked lists, stacks, or queues, trees are non-linear and allow efficient data organization.

A tree consists of nodes, where each node contains:

• Data

• Links to child nodes

The topmost node is called the root, and nodes with no children are called leaf nodes.

Why Trees Are Important

Trees are incredibly powerful and are used in many real-world systems:

• File systems

• Databases and indexing

• Compilers

• Search engines

• XML/HTML structure

• AI search algorithms

Understanding trees is the foundation for learning heaps, tries, AVL trees, red-black trees, and many other advanced structures.

Basic Terminology in Trees

Here are some key terms you must know:

1. Root

The topmost node in a tree.

2. Parent

A node that has one or more child nodes.

3. Child

A node that descends from a parent node.

4. Leaf

A node with no children.

5. Height

The longest path from a node to a leaf.

6. Depth

The distance from the root to a node.

7. Subtree

A smaller tree that exists within a larger tree.

Representation of a Tree

        10
       /  \
     20    30
    /  \     \
   40  50    60

Binary Tree

A binary tree is a type of tree where each node can have at most two children.

     A
    / \
   B   C

Binary trees are the base for several advanced trees such as:

• Binary Search Trees (BST)

• AVL Trees

• Red-Black Trees

• Heaps

Types of Binary Trees

1. Full Binary Tree

Every node has either 0 or 2 children.

2. Complete Binary Tree

All levels are completely filled except possibly the last level.

3. Perfect Binary Tree

All leaf nodes are at the same level.

4. Skewed Tree

Nodes have only one child, making the tree behave like a linked list.

Implementing a Binary Tree Node

public class Node
{
    public int Data;
    public Node Left;
    public Node Right;
}

Tree Traversal Methods

Traversal means visiting each node.
There are two types:

• Depth-First Search (DFS)

• Breadth-First Search (BFS)

DFS Traversals

1. Inorder (Left, Root, Right)

void Inorder(Node root)
{
    if (root == null) return;
    Inorder(root.Left);
    Console.Write(root.Data + " ");
    Inorder(root.Right);
}

2. Preorder (Root, Left, Right)

void Preorder(Node root)
{
    if (root == null) return;
    Console.Write(root.Data + " ");
    Preorder(root.Left);
    Preorder(root.Right);
}

3. Postorder (Left, Right, Root)

void Postorder(Node root)
{
    if (root == null) return;
    Postorder(root.Left);
    Postorder(root.Right);
    Console.Write(root.Data + " ");
}

BFS Traversal (Level Order Traversal)

Uses a queue.

void LevelOrder(Node root)
{
    if (root == null) return;

    Queue<Node> q = new Queue<Node>();
    q.Enqueue(root);

    while (q.Count > 0)
    {
        Node current = q.Dequeue();
        Console.Write(current.Data + " ");

        if (current.Left != null) q.Enqueue(current.Left);
        if (current.Right != null) q.Enqueue(current.Right);
    }
}

Applications of Trees

1. File and Folder Structure

Each directory contains files and subdirectories.

2. Databases (B-Trees, B+ Trees)

Used for indexing millions of records.

3. Artificial Intelligence

Decision trees and game trees.

4. Expression Evaluation

Used by compilers.

5. Routing Algorithms

Used in networks.

Advantages of Trees

• Fast searching and sorting

• Easy to represent hierarchical data

• Better organization of data

Disadvantages of Trees

• Can become unbalanced

• Slower than arrays for random access

• Requires pointers, which use extra memory

Example Problem: Count Nodes in a Binary Tree

int CountNodes(Node root)
{
    if (root == null) return 0;
    return 1 + CountNodes(root.Left) + CountNodes(root.Right);
}

Summary

Trees are one of the most fundamental and versatile data structures in computer science. They are used to represent hierarchical data and enable fast searching and organization.

Key takeaways:

• Trees follow parent–child relationships

• Binary trees have at most two children per node

• Traversals help process nodes in specific orders

• Trees are used in databases, compilers, file systems, and AI