Example usage

After grasping the overall framework of data structures, our previous article explored the fundamental concepts and applications of stacks and queues. Next, we will focus on two essential data structures: trees and graphs. Trees and graphs play a pivotal role in computer science and are widely applied in domains such as databases, networking, routing, compilers, and more.

I. Trees

1. What Is a Tree?

A tree is a hierarchical data structure composed of nodes. Each node may have zero or more child nodes, but exactly one parent node—except for the topmost node, called the root. Key properties of trees include:

• Acyclicity: No cycles exist in a tree.
• Hierarchy: Nodes exhibit a layered relationship—e.g., the root resides at level 0, its children at level 1, and so on.

2. Types of Trees

• Binary Tree: Each node has at most two children—designated left and right.
• Balanced Tree: All leaf nodes reside at the same depth.
• Binary Search Tree (BST): For every node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater.

3. Common Tree Operations

Core tree operations include insertion, deletion, and traversal. Below is a Python implementation of insertion into a binary search tree:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

# Example usage
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)

Here, the Node class models a tree node, and the insert function recursively inserts a new key into the BST while preserving BST ordering.

4. Tree Traversal

Tree traversal follows three primary orders:

• Pre-order: Root → Left → Right
• In-order: Left → Root → Right
• Post-order: Left → Right → Root

Below is an implementation of in-order traversal:

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

# Print tree contents using in-order traversal
inorder_traversal(r)  # Output: 20 30 40 50 60 70 80

II. Graphs

1. What Is a Graph?

A graph is a non-linear data structure consisting of vertices (or nodes) connected by edges. Unlike trees, graphs may contain cycles, and connections between vertices are many-to-many—i.e., any vertex can connect to multiple others, and vice versa.

2. Graph Representations

Graphs can be represented in two principal ways:

• Adjacency Matrix: A 2D array where matrix[i][j] == 1 indicates an edge from vertex i to vertex j.
• Adjacency List: A collection (e.g., dictionary or linked list) mapping each vertex to its neighboring vertices.

Here’s an adjacency matrix representation of an undirected graph:

# Adjacency matrix for an undirected graph
graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

3. Graph Traversal

Two fundamental graph traversal algorithms are:

• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.
• Breadth-First Search (BFS): Explores all neighbors at the present depth before moving to nodes at the next depth level.

Below is a recursive DFS implementation:

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in range(len(graph[v])):
        if graph[v][i] == 1 and not visited[i]:
            dfs(graph, i, visited)

# Example usage
visited = [False] * len(graph)
dfs(graph, 0, visited)  # Start DFS from vertex 0

Conclusion

In this tutorial, we provided a comprehensive overview of trees and graphs—covering their definitions, classifications, and core operations. Trees offer an elegant way to organize hierarchical data, whereas graphs model richer, more complex relationships among entities. Understanding these foundational structures is indispensable for subsequent algorithm analysis—especially when evaluating time complexity.

In the next article, we’ll delve into Algorithm Analysis: Time Complexity, continuing our exploration of core algorithmic concepts. We hope this material deepens your understanding of trees and graphs!