What is the difference between a tree and a graph?

A tree is a special type of graph that is connected, acyclic, and has exactly V-1 edges for V vertices. Every tree is a graph, but not every graph is a tree. Graphs can have cycles, be disconnected, and have any number of edges. Trees have a hierarchical parent-child structure; graphs model arbitrary relationships.

When should I use BFS vs DFS?

Use BFS when you need the shortest path in an unweighted graph, or when you want to explore nodes level by level (e.g., finding the minimum number of moves in a puzzle). Use DFS when you need to explore all paths (e.g., maze solving), detect cycles, perform topological sorting, or when memory is a concern (DFS uses O(h) space vs BFS O(w) where h is height and w is width).

Why can a Binary Search Tree degrade to O(N) performance?

If elements are inserted in sorted (or reverse-sorted) order, the BST becomes a skewed tree resembling a linked list. Every node has only one child, so the height becomes N instead of log N. Self-balancing trees like AVL trees and Red-Black trees prevent this by automatically rebalancing after insertions and deletions, guaranteeing O(log N) height.

What is the difference between an adjacency matrix and an adjacency list?

An adjacency matrix is a V x V grid that allows O(1) edge lookups but uses O(V^2) space. An adjacency list stores only existing edges using O(V + E) space. For sparse graphs (few edges relative to vertices), adjacency lists are more space-efficient. For dense graphs or when frequent edge-existence checks are needed, matrices may be preferable.

What is a cycle in a graph and why does it matter?

A cycle is a path that starts and ends at the same vertex with at least one edge. Cycles matter because: (1) trees are defined as acyclic graphs, (2) graph traversals must track visited nodes to avoid infinite loops in cyclic graphs, (3) cycle detection is essential for dependency resolution (e.g., detecting circular imports), and (4) directed acyclic graphs (DAGs) have special properties useful for scheduling and topological sorting.

What are the real-world applications of trees and graphs?

Trees are used in file systems, DOM trees in web browsers, database indexing (B-trees), compilers (abstract syntax trees), and decision-making (decision trees). Graphs are used in social networks, GPS navigation (shortest path), internet routing, recommendation systems, dependency management (package managers), and knowledge graphs. Nearly every complex system can be modeled as a tree or graph.

Computer ScienceCollege

Trees & Graphs

Trees and graphs are fundamental non-linear data structures in computer science. Trees model hierarchical relationships with a single root and no cycles, while graphs offer a more general model for arbitrary connections and complex networks.

This guide covers tree and graph terminology, binary search tree operations, BFS and DFS traversals, graph representations (adjacency matrix vs adjacency list), complexity analysis, code walkthroughs, and a 10-question practice quiz.

Tree Traversal Visualizer

DFS

BFS: Level by level (Queue)

CurrentVisitedUnvisited

Queue (FIFO)

Empty

Output Order

No nodes visited yet

Click Play or Step Forward to begin BFS traversal.

Step 0 / 6

BFS explores level by level using a queue. Preorder visits the root first, then left, then right. Inorder visits left, then root, then right (gives sorted order on BSTs). Postorder visits children before the parent.

1Introduction

Trees and graphs are non-linear data structures that organize data beyond simple sequential arrangements. While arrays and linked lists store elements in a line, trees and graphs capture relationships between data elements — hierarchical (parent-child) in trees, and arbitrary (networked) in graphs.

These structures are central to nearly every area of computer science: file systems (directory trees), databases (B-tree indexing), compilers (abstract syntax trees), social networks (friend graphs), GPS navigation (shortest-path algorithms), and AI (game trees, knowledge graphs). Understanding trees and graphs is essential for efficient algorithm design and problem-solving.

In Practice

Every time you browse a file system, use Google Maps, scroll through a social media feed, or run a package manager like npm, you are interacting with tree and graph algorithms behind the scenes. Mastering these data structures unlocks the ability to model and solve problems involving hierarchy, connectivity, and networks.

Binary tree structure diagram showing root, internal nodes, and leaf nodes with labels

2Key Definitions

Essential terms for understanding trees and graphs at the university level.

Node (Vertex)

Fundamental unit containing data and references to other nodes

Edge

Connection between two nodes; can be directed or undirected

Root

Topmost node in a tree; has no parent; exactly one per tree

Leaf

Node with no children (external node); terminal point in a tree

Depth

Number of edges from the root to a node; root depth = 0

Height

Number of edges on the longest path from a node to a leaf

Cycle

Path that starts and ends at the same vertex; trees have none

Path

Sequence of connected nodes from one node to another

Degree

Number of edges incident to a vertex (children in trees)

Connected Graph

A path exists between every pair of vertices

Directed Graph (Digraph)

Edges have direction; one-way from source to destination

Weighted Graph

Each edge has a numerical weight (cost, distance, capacity)

Adjacency List

Graph representation mapping each vertex to its neighbors; O(V+E) space

Adjacency Matrix

V x V matrix for edge lookups in O(1); O(V²) space

Binary Search Tree

Binary tree where left < root < right for every node

Spanning Tree

A subgraph that is a tree connecting all vertices with minimum edges

3Tree Fundamentals

A tree is a connected, acyclic graph with a designated root node. For V vertices, a tree has exactly V−1 edges. Trees organize data hierarchically, making them ideal for representing file systems, organizational structures, and parsed expressions.

Types of Binary Trees

Full Binary Tree

Every node has either 0 or 2 children. No node has exactly one child.

Complete Binary Tree

All levels fully filled except possibly the last, which is filled left to right. Used in heaps.

Perfect Binary Tree

All internal nodes have 2 children and all leaves are at the same depth. Has 2^h+1−1 nodes.

Skewed Binary Tree

All nodes have only a left or only a right child. Degenerates into a linked list with O(N) operations.

Specialized Tree Types

Balanced Trees (AVL, Red-Black) maintain logarithmic height through rotations, guaranteeing O(log N) for all operations. Heaps are complete binary trees satisfying the heap property (max-heap: parent ≥ children), used for priority queues. Tries (prefix trees) store strings character-by-character for efficient prefix lookups.

Binary Search Tree example showing left subtree values less than root and right subtree values greater

4Binary Search Trees

A Binary Search Tree (BST) is a binary tree where every node satisfies: all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering enables efficient search, insertion, and deletion.

BST Operations

Start at root. If target < node, go left. If target > node, go right. If equal, found.

Average: O(log N) | Worst (skewed): O(N)

Insert

Follow the search path. When reaching a null child in the correct direction, insert the new node there.

Average: O(log N) | Worst (skewed): O(N)

BST Complexity Summary

Operation	Average Case	Worst Case	Space
Search	O(log N)	O(N)	O(H)
Insert	O(log N)	O(N)	O(H)
Delete	O(log N)	O(N)	O(H)
Traversal	O(N)	O(N)	O(H)

H = height of the tree. For a balanced BST, H = O(log N). For a skewed BST, H = O(N).

Balance Matters

Inserting sorted data into a plain BST creates a skewed tree with O(N) operations. Self-balancing trees (AVL, Red-Black) automatically maintain O(log N) height through rotations after each insertion or deletion.

5Graph Fundamentals

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices. Graphs model arbitrary relationships — social connections, road networks, dependency chains — and are more general than trees.

Different graph types: undirected, directed, weighted, and cyclic graphs

Directed vs. Undirected

Undirected Graph

Edges have no direction — relationships are bidirectional. An edge {u, v} means both u→v and v→u.

Example: Facebook friendships, road networks

Directed Graph (Digraph)

Edges have direction — one-way relationships. An edge (u, v) means u→v only.

Example: Twitter follows, web page links

Graph Representations

Adjacency Matrix

V × V matrix
O(1) edge lookup
O(V²) space
Best for dense graphs

Adjacency List

Map: vertex → list of neighbors
O(degree) edge lookup
O(V + E) space
Best for sparse graphs

Trees vs. Graphs

Feature	Tree	Graph
Cycles	None (acyclic)	Can have cycles
Connectivity	Must be connected	Can be disconnected
Root	Exactly one	No designated root
Edges	V − 1	0 to V(V−1)/2
Hierarchy	Parent-child	Arbitrary

6Traversal Algorithms

Traversal is the process of visiting every node exactly once. The two primary strategies — Breadth-First Search (BFS) and Depth-First Search (DFS) — apply to both trees and graphs.

BFS vs DFS traversal comparison showing level-order versus depth-first exploration

Breadth-First Search (BFS)

BFS explores level by level, visiting all neighbors of the current node before moving deeper. It uses a queue (FIFO) to maintain the frontier.

Start at source. Mark visited. Enqueue.
While queue not empty: dequeue u, visit all unvisited neighbors of u, enqueue them.
Guarantees shortest path in unweighted graphs.

Time: O(V + E)Space: O(V)

Depth-First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It uses a stack (explicit or via recursion).

Start at source. Mark visited.
For each unvisited neighbor: recursively DFS on it.
Useful for topological sort, cycle detection, and pathfinding.

Time: O(V + E)Space: O(V)

Tree Traversal Orders (DFS Variants)

Inorder

Left → Root → Right

Yields sorted order in BST

Preorder

Root → Left → Right

Useful for copying a tree

Postorder

Left → Right → Root

Useful for deleting a tree

Tree traversal orders: inorder, preorder, postorder, and level-order visit sequences

7Code Walkthroughs

Introductory

Binary Tree Inorder Traversal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder(node):
    if not node:
        return            # Base case: empty subtree
    inorder(node.left)    # Recurse left subtree
    print(node.val)       # Visit current node
    inorder(node.right)   # Recurse right subtree

Line 8: Base case — if the node is None, return immediately (empty subtree).

Line 10: Recurse into the left subtree first (all smaller values in a BST).

Line 11: Visit (print) the current node after left subtree is fully processed.

Line 12: Then recurse into the right subtree (all larger values in a BST).

Time: O(n)Space: O(h)

Key insight: The three traversal orders (inorder, preorder, postorder) differ only in when the root is visited relative to left and right subtrees.

Introductory

Binary Search Tree Search

def bst_search(node, target):
    if not node or node.val == target:
        return node           # Found or reached null
    if target < node.val:
        return bst_search(node.left, target)   # Go left
    return bst_search(node.right, target)      # Go right

Line 2: Base cases — either the node is null (not found) or we found the target value.

Line 4–5: If target is less than current value, it must be in the left subtree (BST property).

Line 6: Otherwise, the target must be in the right subtree.

Time: O(h) — O(log n) balancedSpace: O(h)

Key insight: BST search eliminates half the remaining tree at each step, similar to binary search on a sorted array.

Intermediate

BFS Graph Traversal

from collections import deque

def bfs(graph, start):
    visited = set([start])       # Track visited nodes
    queue = deque([start])       # Initialize queue with start
    result = []

    while queue:
        node = queue.popleft()   # Dequeue front node
        result.append(node)      # Process it

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # Mark before enqueue
                queue.append(neighbor) # Enqueue neighbor

    return result

Line 4: The visited set prevents revisiting nodes in cyclic graphs — essential to avoid infinite loops.

Line 5: A deque provides O(1) popleft, unlike a list which is O(n).

Line 9: Dequeue from front ensures level-by-level (breadth-first) exploration.

Line 14: Mark as visited before enqueueing to prevent duplicate entries in the queue.

Time: O(V + E)Space: O(V)

Key insight: BFS explores all nodes at distance d before any node at distance d+1, guaranteeing shortest paths in unweighted graphs.

Intermediate

DFS Graph Traversal (Recursive)

def dfs(graph, node, visited):
    visited.add(node)            # Mark as visited
    result = [node]              # Process current node

    for neighbor in graph[node]:
        if neighbor not in visited:
            result += dfs(graph, neighbor, visited)  # Recurse

    return result

# Usage:
# visited = set()
# order = dfs(graph, start_node, visited)

Line 1: The visited set is passed by reference, shared across all recursive calls.

Line 2: Mark as visited immediately to prevent revisiting from other paths.

Line 7: Recurse on unvisited neighbors — explores as deep as possible before backtracking.

Time: O(V + E)Space: O(V)

Key insight: DFS uses the call stack implicitly. For very deep graphs, an iterative version with an explicit stack avoids stack overflow.

8Memory Aids

BFS vs DFS

“BFS = ripples in a pond (spreads outward layer by layer). DFS = exploring a maze (go deep, hit a wall, backtrack).”

Queue vs Stack

“BFS uses a Queue (both start with consonants after B/Q). DFS uses a Stack (both have S).”

BST Property

“Left is Less, Right is gReater” — the BST invariant in six words.

Tree vs Graph

“A tree is a family tree (hierarchy, no loops). A graph is a social network (anyone can connect to anyone, loops allowed).”

Inorder Traversal

“Inorder on a BST = sorted order” — if your inorder output isn't sorted, your BST is broken.

Graph Representation

“Matrix for dense, List for sparse” — most real-world graphs are sparse, so adjacency lists are the default choice.

9Common Mistakes

Forgetting the Visited Set in Graph Traversals

Without tracking visited nodes, BFS/DFS on graphs with cycles will loop forever.

Always initialize a visited set or boolean array before traversal. Mark nodes as visited before enqueueing/pushing to prevent duplicate processing.

Confusing Trees with General Graphs

Assuming tree algorithms work on arbitrary graphs without modification.

Trees are acyclic and connected with V−1 edges. Graphs may have cycles and disconnected components. Tree traversals don't need a visited set; graph traversals do.

Ignoring Disconnected Components

Running BFS/DFS from a single node and assuming the entire graph is traversed.

A single BFS/DFS only visits nodes reachable from the start vertex. To traverse all components, loop through all vertices and start a new traversal from any unvisited node.

Assuming All BSTs Are Balanced

Claiming BST operations are always O(log N).

A plain BST can degrade to O(N) if data is inserted in sorted order. Only self-balancing BSTs (AVL, Red-Black) guarantee O(log N). Always specify “balanced BST” when claiming logarithmic performance.

Missing Base Case in Tree Recursion

Forgetting to check for null/None nodes before accessing children.

Every recursive tree function must handle the empty subtree case: if not node: return. Without this, you'll get NullPointerException or AttributeError.

Wrong Representation for the Problem

Using an adjacency matrix for a sparse graph with millions of vertices.

An adjacency matrix uses O(V²) space regardless of edge count. For sparse graphs (E << V²), adjacency lists use O(V + E) space and make neighbor iteration proportional to degree, not V.

Stack Overflow on Deep Recursive DFS

Using recursive DFS on a graph with very long paths or a deep tree.

Python's default recursion limit is ~1000. For large inputs, convert recursive DFS to iterative DFS with an explicit stack, or increase the recursion limit carefully.

Off-by-One in Depth/Height

Mixing up whether depth/height counts nodes or edges.

Standardize your definition: depth = number of edges from root to node (root depth = 0). Height = number of edges on the longest path from a node to a leaf (leaf height = 0). Stick to one convention consistently.

Frequently Asked Questions

What is the difference between a tree and a graph?: A tree is a special type of graph that is connected, acyclic, and has exactly V-1 edges for V vertices. Every tree is a graph, but not every graph is a tree. Graphs can have cycles, be disconnected, and have any number of edges. Trees have a hierarchical parent-child structure; graphs model arbitrary relationships.
When should I use BFS vs DFS?: Use BFS when you need the shortest path in an unweighted graph, or when you want to explore nodes level by level (e.g., finding the minimum number of moves in a puzzle). Use DFS when you need to explore all paths (e.g., maze solving), detect cycles, perform topological sorting, or when memory is a concern (DFS uses O(h) space vs BFS O(w) where h is height and w is width).
Why can a Binary Search Tree degrade to O(N) performance?: If elements are inserted in sorted (or reverse-sorted) order, the BST becomes a skewed tree resembling a linked list. Every node has only one child, so the height becomes N instead of log N. Self-balancing trees like AVL trees and Red-Black trees prevent this by automatically rebalancing after insertions and deletions, guaranteeing O(log N) height.
What is the difference between an adjacency matrix and an adjacency list?: An adjacency matrix is a V x V grid that allows O(1) edge lookups but uses O(V^2) space. An adjacency list stores only existing edges using O(V + E) space. For sparse graphs (few edges relative to vertices), adjacency lists are more space-efficient. For dense graphs or when frequent edge-existence checks are needed, matrices may be preferable.
What is a cycle in a graph and why does it matter?: A cycle is a path that starts and ends at the same vertex with at least one edge. Cycles matter because: (1) trees are defined as acyclic graphs, (2) graph traversals must track visited nodes to avoid infinite loops in cyclic graphs, (3) cycle detection is essential for dependency resolution (e.g., detecting circular imports), and (4) directed acyclic graphs (DAGs) have special properties useful for scheduling and topological sorting.
What are the real-world applications of trees and graphs?: Trees are used in file systems, DOM trees in web browsers, database indexing (B-trees), compilers (abstract syntax trees), and decision-making (decision trees). Graphs are used in social networks, GPS navigation (shortest path), internet routing, recommendation systems, dependency management (package managers), and knowledge graphs. Nearly every complex system can be modeled as a tree or graph.

Practice Quiz

Test your understanding of trees and graphs — select the correct answer for each question.

1.What is the maximum number of children a node can have in a binary tree?

2.Which tree traversal order visits nodes in ascending order of their values in a Binary Search Tree (BST)?

3.What is the depth of the root node in a tree?

4.Which data structure is typically used to implement Breadth-First Search (BFS)?

5.A graph where edges have a direction is called a:

6.What is the time complexity to check if an edge exists between two vertices in an adjacency matrix?

7.Which of the following statements about trees and graphs is true?

8.If a Binary Search Tree becomes completely skewed (like a linked list), what is the worst-case time complexity for searching?

9.Which graph traversal algorithm is best suited for finding the shortest path in an unweighted graph?

10.What is a common pitfall when implementing BFS or DFS on graphs that contain cycles?

Study Tips

Draw it out: Sketch trees and graphs by hand when working through problems. Trace BFS and DFS step by step, maintaining the queue/stack on paper.
Implement from scratch: Code a BST with insert, search, and all four traversals. Then implement BFS and DFS on an adjacency list. This builds deep understanding.
Compare BFS and DFS: Run both on the same graph and compare visit orders, memory usage, and which one finds shortest paths.
Practice on LeetCode: Start with easy tree problems (inorder traversal, max depth) then progress to graph problems (number of islands, course schedule).

Tree Traversal Visualizer

1Introduction

2Key Definitions

3Tree Fundamentals

Types of Binary Trees

Specialized Tree Types

4Binary Search Trees

BST Operations

BST Complexity Summary

5Graph Fundamentals

Directed vs. Undirected

Graph Representations

Trees vs. Graphs

6Traversal Algorithms

Breadth-First Search (BFS)

Depth-First Search (DFS)

Tree Traversal Orders (DFS Variants)

7Code Walkthroughs

8Memory Aids

9Common Mistakes

Frequently Asked Questions

Practice Quiz

Study Tips

Related Topics