Tree & Graph Data Structures

Non-Linear Data Structures: Tree and Graph

While arrays, linked lists, stacks, and queues are linear data structures where data is arranged sequentially, Trees and Graphs are non-linear data structures. They organize data hierarchically or interconnectedly, making them ideal for representing complex relationships like family trees, organizational charts, or computer networks.

1. Tree Data Structure

1.1 Basic Terminology

• Node: An entity that contains a key or value and pointers to its child nodes.
• Root: The topmost node in the tree hierarchy. It has no parent.
• Edge: The link connecting two nodes.
• Parent: Any node (except root) has one edge upward to a node called parent.
• Child: The node below a given node connected by its edge downward.
• Leaf (External Node): A node that has no children.
• Internal Node: A node with at least one child.
• Depth of a Node: The number of edges from the root to the node.
• Height of a Node: The number of edges on the longest path from the node to a leaf.
• Height of a Tree: The height of its root node.

1.2 Binary Tree

1. Full Binary Tree (Strict Binary Tree): Every node has either 0 or 2 children.
2. Complete Binary Tree: All levels are completely filled except possibly the last level, and the last level has all keys as left as possible (like a Binary Heap).
3. Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same level.
4. Balanced Binary Tree: The left and right subtrees of every node differ in height by no more than 1 (e.g., AVL tree, Red-Black tree).
5. Degenerate (Pathological) Tree: Every internal node has only one child. It essentially behaves like a linked list.

1.3 Binary Search Tree (BST)

• The left subtree of a node contains only nodes with keys lesser than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtrees each must also be a binary search tree. Operations on BST:
• Search: O(log N) average, O(N) worst case.
• Insertion: O(log N) average, O(N) worst case.
• Deletion: O(log N) average, O(N) worst case.

1.4 Tree Traversals

1. Inorder Traversal (Left, Root, Right):
   • Gives nodes in non-decreasing (sorted) order for a BST.
   • Algorithm: Traverse Left Subtree -> Visit Root -> Traverse Right Subtree.
2. Preorder Traversal (Root, Left, Right):
   • Used to create a copy of the tree or to get prefix expressions.
   • Algorithm: Visit Root -> Traverse Left Subtree -> Traverse Right Subtree.
3. Postorder Traversal (Left, Right, Root):
   • Used to delete the tree or to get postfix expressions.
   • Algorithm: Traverse Left Subtree -> Traverse Right Subtree -> Visit Root. B. Breadth-First Traversal (BFS):
4. Level Order Traversal:
   • Visits nodes level by level from left to right. Implemented using a Queue.

2. Graph Data Structure

2.1 Basic Terminology

• Vertex: A node in the graph.
• Edge: A connection between two vertices.
• Directed Graph (Digraph): Edges have a direction (indicated by arrows).
• Undirected Graph: Edges do not have a direction. The connection is two-way.
• Weighted Graph: Edges have weights or costs associated with them.
• Degree: The number of edges connected to a vertex.
• In-Degree (Digraph): Number of edges coming into a vertex.
• Out-Degree (Digraph): Number of edges going out of a vertex.
• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.

2.2 Graph Representation

• A 2D array of size V x V where V is the number of vertices.
• adj[i][j] = 1 indicates an edge from vertex i to vertex j. (In a weighted graph, it holds the weight).
• Pros: Easy to implement, O(1) to check if an edge exists.
• Cons: Consumes O(V^2) space, which is inefficient for sparse graphs. 2. Adjacency List:
• An array of Linked Lists (or dynamic arrays). The size of the array is equal to the number of vertices.
• adj[i] contains a list of all vertices connected to vertex i.
• Pros: Saves space O(V + E). Efficient for sparse graphs.
• Cons: O(V) time to check if an edge exists between two specific vertices.

2.3 Graph Traversals

1. Breadth-First Search (BFS):
   • Traverses level by level.
   • Uses a Queue data structure.
   • Useful for finding the shortest path on unweighted graphs.
   • Time Complexity: O(V + E).
2. Depth-First Search (DFS):
   • Traverses as deep as possible before backtracking.
   • Uses a Stack data structure (or recursion).
   • Useful for topological sorting, cycle detection, and solving puzzles like mazes.
   • Time Complexity: O(V + E).

2.4 Important Graph Algorithms (Overview)

• Minimum Spanning Tree (MST): A subset of edges that connects all vertices with the minimum possible total edge weight, without any cycles.
  • Prim's Algorithm: Builds MST by picking the smallest edge connected to the growing MST.
  • Kruskal's Algorithm: Builds MST by sorting all edges and adding them one by one if they don't form a cycle (using Disjoint Set).
• Shortest Path Algorithms:
  • Dijkstra's Algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph (with non-negative weights).
  • Bellman-Ford Algorithm: Finds shortest path from source and can handle negative weight edges.
  • Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices.