Trees & Graphs

Trees and graphs are non-linear data structures that represent hierarchical or network relationships between objects.

Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has a root node, and every node has zero or more child nodes.

Types of Trees

1. Binary Tree: Each node has at most two children
2. Binary Search Tree (BST): A binary tree where left children are less than the parent, and right children are greater
3. AVL Tree: A self-balancing BST
4. Red-Black Tree: A self-balancing BST with additional properties
5. Trie: A tree-like data structure for storing strings

Graphs

A graph is a collection of nodes connected by edges. Unlike trees, graphs can have cycles.

Types of Graphs

1. Directed Graph: Edges have a direction
2. Undirected Graph: Edges have no direction
3. Weighted Graph: Edges have weights or costs
4. Connected Graph: There is a path between every pair of vertices
5. Disconnected Graph: There are vertices that cannot be reached from others

Key Algorithms

1. Tree Traversals: Inorder, Preorder, Postorder
2. Graph Traversals: Breadth-First Search (BFS), Depth-First Search (DFS)
3. Shortest Path: Dijkstra's Algorithm, Bellman-Ford Algorithm
4. Minimum Spanning Tree: Prim's Algorithm, Kruskal's Algorithm

Common Problems

1. Maximum Depth of Binary Tree
2. Validate Binary Search Tree
3. Binary Tree Level Order Traversal
4. Number of Islands
5. Course Schedule (Graph Cycle Detection)