Review of Tree and Graph Structures
1. Tree Structures
A tree is a hierarchical data structure composed of nodes, where each node has a
parent-child relationship with others. Trees are widely used in databases, artificial
intelligence, computer networks, and more.
Key Characteristics of Trees:
• Hierarchical Structure: Nodes are arranged in a hierarchical manner.
• One Root Node: A tree has a single root node from which all other nodes
descend.
• Parent-Child Relationship: Each node (except the root) has exactly one parent
but can have multiple children.
• No Cycles: Trees do not contain cycles (loops).
Types of Trees:
1. Binary Tree: Each node has at most two children (left and right).
2. Binary Search Tree (BST): A binary tree where the left child contains smaller
values and the right child contains larger values.
3. Balanced Trees (AVL, Red-Black Tree): Trees that maintain balance to
optimize search operations.
4. Heap: A complete binary tree used in priority queues (Min-Heap and Max-
Heap).
5. B-Trees and B+ Trees: Used in databases for efficient indexing and searching.
Common Operations in Trees:
• Insertion: Adding a new node to the tree.
• Deletion: Removing a node while maintaining tree properties.
• Traversal: Visiting nodes in a specific order (Preorder, Inorder, Postorder,
Level Order).
• Searching: Finding a specific node based on value.
2. Graph Structures
A graph is a data structure that consists of nodes (vertices) and edges (connections)
between them. Graphs are used in networking, social media, route planning, AI, and
many other applications.
Key Characteristics of Graphs:
• Consists of Vertices and Edges: A graph is defined as G = (V, E) where V
represents vertices and E represents edges.
• Can be Directed or Undirected:
o Directed Graph (Digraph): Edges have a direction (e.g., one-way
streets).
o Undirected Graph: Edges do not have a direction (e.g., friendships on
social media).
• Can be Weighted or Unweighted:
o Weighted Graph: Edges have associated weights (e.g., road distances).
o Unweighted Graph: Edges have no weights (e.g., simple connections).
• Can Have Cycles or Be Acyclic:
o Cyclic Graph: Contains cycles.
o Acyclic Graph: Does not contain cycles.
Types of Graphs:
1. Adjacency Matrix Representation: Uses a 2D matrix to store edges between
vertices.
2. Adjacency List Representation: Uses lists to store neighboring nodes.
3. Connected Graph: Every vertex is reachable from any other vertex.
4. Disconnected Graph: Some vertices are not connected.
5. Complete Graph: Every pair of vertices is connected by an edge.
6. Bipartite Graph: Vertices can be divided into two sets with edges only between
different sets.
7. DAG (Directed Acyclic Graph): Used in scheduling problems and compiler
optimizations.
Common Operations in Graphs:
• Graph Traversal:
o Depth-First Search (DFS): Explores as deep as possible before
backtracking.
o Breadth-First Search (BFS): Explores all neighbors before going deeper.
• Shortest Path Algorithms:
o Dijkstra’s Algorithm: Finds the shortest path in weighted graphs.
o Bellman-Ford Algorithm: Works for graphs with negative weights.
o Floyd-Warshall Algorithm: Finds shortest paths between all pairs of
nodes.
• Minimum Spanning Tree (MST):
o Kruskal’s Algorithm and Prim’s Algorithm for finding MST.
• Topological Sorting: Used for scheduling tasks with dependencies in DAGs.
Comparison between Tree and Graph structures
