Understanding Data Structures: Trees and Graphs

Trees and graphs are fundamental data structures that power everything from file systems to social networks. In this guide, we'll visualize these structures, understand their properties, and implement them from scratch.

What Are Trees?#

A tree is a hierarchical data structure consisting of nodes connected by edges. Every tree has exactly one root node, and each node can have zero or more child nodes.

Rendering diagram...

Binary Trees#

A binary tree is a tree where each node has at most two children, typically called "left" and "right".

Rendering diagram...

Binary Tree Implementation#

class TreeNode<T> {
    value: T;
    left: TreeNode<T> | null = null;
    right: TreeNode<T> | null = null;

    constructor(value: T) {
        this.value = value;
    }
}

class BinaryTree<T> {
    root: TreeNode<T> | null = null;

    // In-order traversal: Left -> Root -> Right
    inOrder(node: TreeNode<T> | null = this.root): T[] {
        if (!node) return [];
        return [
            ...this.inOrder(node.left),
            node.value,
            ...this.inOrder(node.right)
        ];
    }

    // Pre-order traversal: Root -> Left -> Right
    preOrder(node: TreeNode<T> | null = this.root): T[] {
        if (!node) return [];
        return [
            node.value,
            ...this.preOrder(node.left),
            ...this.preOrder(node.right)
        ];
    }

    // Post-order traversal: Left -> Right -> Root
    postOrder(node: TreeNode<T> | null = this.root): T[] {
        if (!node) return [];
        return [
            ...this.postOrder(node.left),
            ...this.postOrder(node.right),
            node.value
        ];
    }
}

Binary Search Trees (BST)#

A BST maintains an ordering property: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger.

Time Complexity Analysis#

The efficiency of BST operations depends on the tree's balance:

Operation	Average Case	Worst Case
Search	$O(\log n)$	$O(n)$
Insert	$O(\log n)$	$O(n)$
Delete	$O(\log n)$	$O(n)$

The worst case occurs when the tree becomes a linear chain (completely unbalanced).

class BinarySearchTree<T> extends BinaryTree<T> {
    insert(value: T): void {
        const newNode = new TreeNode(value);

        if (!this.root) {
            this.root = newNode;
            return;
        }

        this.insertNode(this.root, newNode);
    }

    private insertNode(node: TreeNode<T>, newNode: TreeNode<T>): void {
        if (newNode.value < node.value) {
            if (!node.left) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (!node.right) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    search(value: T): TreeNode<T> | null {
        return this.searchNode(this.root, value);
    }

    private searchNode(
        node: TreeNode<T> | null,
        value: T
    ): TreeNode<T> | null {
        if (!node || node.value === value) {
            return node;
        }

        if (value < node.value) {
            return this.searchNode(node.left, value);
        }
        return this.searchNode(node.right, value);
    }
}

Self-Balancing Trees#

To guarantee $O(\log n)$ operations, we use self-balancing trees like AVL or Red-Black trees.

AVL Tree Rotations#

Rendering diagram...

Introduction to Graphs#

Unlike trees, graphs can have cycles and multiple paths between nodes. They're used to model networks, relationships, and many real-world problems.

Rendering diagram...

Graph Types#

Type	Description
Directed	Edges have direction (one-way)
Undirected	Edges are bidirectional
Weighted	Edges have associated costs
Cyclic	Contains at least one cycle
Acyclic	No cycles (DAG if directed)

Graph Representation#

Adjacency Matrix#

Best for dense graphs where $E \approx V^2$ :

class AdjacencyMatrix {
    private matrix: number[][];
    private vertices: number;

    constructor(vertices: number) {
        this.vertices = vertices;
        this.matrix = Array(vertices)
            .fill(null)
            .map(() => Array(vertices).fill(0));
    }

    addEdge(from: number, to: number, weight: number = 1): void {
        this.matrix[from][to] = weight;
        // For undirected graph:
        // this.matrix[to][from] = weight;
    }

    hasEdge(from: number, to: number): boolean {
        return this.matrix[from][to] !== 0;
    }

    getWeight(from: number, to: number): number {
        return this.matrix[from][to];
    }
}

Space complexity: $O(V^2)$

Adjacency List#

Better for sparse graphs:

class AdjacencyList<T> {
    private adjacencyList: Map<T, Array<{ node: T; weight: number }>>;

    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(vertex: T): void {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }

    addEdge(from: T, to: T, weight: number = 1): void {
        this.addVertex(from);
        this.addVertex(to);
        this.adjacencyList.get(from)!.push({ node: to, weight });
        // For undirected graph:
        // this.adjacencyList.get(to)!.push({ node: from, weight });
    }

    getNeighbors(vertex: T): Array<{ node: T; weight: number }> {
        return this.adjacencyList.get(vertex) || [];
    }
}

Space complexity: $O(V + E)$

Graph Traversal Algorithms#

Breadth-First Search (BFS)#

BFS explores all neighbors at the current depth before moving deeper:

Rendering diagram...

function bfs<T>(graph: AdjacencyList<T>, start: T): T[] {
    const visited = new Set<T>();
    const queue: T[] = [start];
    const result: T[] = [];

    visited.add(start);

    while (queue.length > 0) {
        const vertex = queue.shift()!;
        result.push(vertex);

        for (const { node } of graph.getNeighbors(vertex)) {
            if (!visited.has(node)) {
                visited.add(node);
                queue.push(node);
            }
        }
    }

    return result;
}

Time complexity: $O(V + E)$

Depth-First Search (DFS)#

DFS explores as far as possible along each branch before backtracking:

function dfs<T>(graph: AdjacencyList<T>, start: T): T[] {
    const visited = new Set<T>();
    const result: T[] = [];

    function traverse(vertex: T): void {
        visited.add(vertex);
        result.push(vertex);

        for (const { node } of graph.getNeighbors(vertex)) {
            if (!visited.has(node)) {
                traverse(node);
            }
        }
    }

    traverse(start);
    return result;
}

Shortest Path: Dijkstra's Algorithm#

For weighted graphs, Dijkstra's algorithm finds the shortest path from a source to all other vertices:

Rendering diagram...

function dijkstra<T>(
    graph: AdjacencyList<T>,
    start: T
): Map<T, number> {
    const distances = new Map<T, number>();
    const visited = new Set<T>();
    const pq: Array<{ node: T; distance: number }> = [];

    // Initialize distances
    distances.set(start, 0);
    pq.push({ node: start, distance: 0 });

    while (pq.length > 0) {
        // Get minimum distance node
        pq.sort((a, b) => a.distance - b.distance);
        const { node: current, distance } = pq.shift()!;

        if (visited.has(current)) continue;
        visited.add(current);

        for (const { node: neighbor, weight } of graph.getNeighbors(current)) {
            const newDist = distance + weight;
            const currentDist = distances.get(neighbor) ?? Infinity;

            if (newDist < currentDist) {
                distances.set(neighbor, newDist);
                pq.push({ node: neighbor, distance: newDist });
            }
        }
    }

    return distances;
}

Time complexity: $O((V + E) \log V)$ with a proper priority queue.

Complexity Comparison#

Here's a summary of time complexities for common operations:

Data Structure	Search	Insert	Delete	Space
Binary Tree	$O(n)$	$O(n)$	$O(n)$	$O(n)$
BST (balanced)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
BST (worst)	$O(n)$	$O(n)$	$O(n)$	$O(n)$
Graph (adj. matrix)	$O(1)$	$O(1)$	$O(1)$	$O(V^2)$
Graph (adj. list)	$O(V)$	$O(1)$	$O(E)$	$O(V+E)$

Practical Applications#

Understanding these data structures is essential for solving complex problems efficiently. Practice implementing them, analyze their trade-offs, and you'll become a more effective problem solver.

Understanding Data Structures: Trees and Graphs

What Are Trees?#

Binary Trees#

Binary Tree Implementation#

Binary Search Trees (BST)#

Time Complexity Analysis#

Self-Balancing Trees#

AVL Tree Rotations#

Introduction to Graphs#

Graph Types#

Graph Representation#

Adjacency Matrix#

Adjacency List#

Graph Traversal Algorithms#

Breadth-First Search (BFS)#

Depth-First Search (DFS)#

Shortest Path: Dijkstra's Algorithm#

Complexity Comparison#

Practical Applications#

Related Articles

Getting Started with TypeScript: A Practical Guide

Top 10 Developer Twitter Posts of 2025

The Mathematics Behind Neural Networks