8. Data Structures in C++: Trees & Graph Traversal

Comprehensive Guide: OOP Linked lists, Binary Search Trees (BST), Graph adjacency lists & BFS/DFS algorithms

Module 1: C++ Object-Oriented Linked List Class

Encapsulating nodes and dynamic operations within a C++ LinkedList class.

🇬🇧 English Definition

An Object-Oriented Linked List wraps dynamic Node structures within a managing LinkedList class exposing public insert, delete, and print methods.

🇮🇳 Hinglish Definition

C++ me Linked List ko Class me wrap karke clean member functions (insert, display) ke through manage kiya jata hai.

Core Concepts & Rules

Node class contains data and Node* next pointer.
LinkedList class encapsulates head pointer and list management methods.

🔍 Line-by-Line Code Breakdown

Line 1-5: Define Node struct with constructor Node(int v) : data(v), next(nullptr) {}.
Line 8-15: LinkedList class with insertAtHead method.

💻 Practical C++ Code Example - C++ Object-Oriented Linked List Class

using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int v) : data(v), next(nullptr) {}
};

class LinkedList {
public:
    Node *head;
    LinkedList() : head(nullptr) {}
    void insert(int v) {
        Node *newNode = new Node(v);
        newNode->next = head;
        head = newNode;
    }
};

int main() {
    LinkedList list;
    list.insert(20);
    list.insert(10);
    cout << "Head Node Data: " << list.head->data << endl;
    return 0;
}

📤 Compiled C++ Output:

Head Node Data: 10

Module 2: C++ Graph Representation (Adjacency List)

Representing non-linear graph networks using vector of vectors.

🇬🇧 English Definition

An Adjacency List represents a graph as an array or vector of vectors, where each index contains a list of neighboring adjacent vertices.

🇮🇳 Hinglish Definition

Graph ko adjacency list me represent karne ke liye vector> graph(V) ka use hota hai jahan har vertex se jude nodes list me store hote hai.

Core Concepts & Rules

Undirected edge (u, v): graph[u].push_back(v); graph[v].push_back(u);
Space complexity: O(V + E).

🔍 Line-by-Line Code Breakdown

Line 4: Create vector adj[3] representing graph with 3 vertices.
Line 5-6: Add edge between vertex 0 and 1.
Line 7: Prints neighbors of vertex 0.

💻 Practical C++ Code Example - C++ Graph Representation (Adjacency List)

using namespace std;

int main() {
    int V = 3;
    vector<int> adj[3];
    adj[0].push_back(1);
    adj[1].push_back(0);

    cout << "Neighbors of Vertex 0: " << adj[0][0] << endl;
    return 0;
}

📤 Compiled C++ Output:

Neighbors of Vertex 0: 1