Python Data Structures

  1.Lists

Python Lists are versatile, ordered collections of items. Unlike arrays in other languages, Python lists can contain elements of different data types. For instance, a single list can hold integers, strings, floats, and more.

In terms of performance, inserting or deleting items at the beginning of a list can be expensive because all subsequent elements must shift to maintain order. Adding or removing items at the end is generally faster, though it can become slower if the underlying memory needs to be resized.

Example:

my_list = [10, "hello", 3.14, True]
print(my_list)

Output:

[10, "hello", 3.14, True]

2.Dictionary

A Python dictionary is a built-in data structure that functions similarly to hash tables in other languages, offering average time complexity of O(1) for key-based lookups. Unlike other data types that hold a single value, dictionaries are collections of key-value pairs, where each key acts as an identifier and each value is the associated data.n short, O(1)O(1) indicates that the operation is fast, efficient, and unaffected by the scale of the data.

Dictionaries do not maintain any specific order (prior to Python 3.7), and keys must be of an immutable type, such as strings, numbers, or tuples. This structure is particularly useful for mapping data, allowing efficient retrieval and updates. You can create dictionaries using curly braces {} or through dictionary comprehensions.

Example:

# Creating a dictionary with various key-value pairs
student_scores = {'Alice': 85, 'Bob': 92, 'Charlie': 78}
print("Student Scores Dictionary:")
print(student_scores)

# Accessing a value by key
print("Score for Alice:")
print(student_scores['Alice'])

# Adding a new key-value pair
student_scores['David'] = 88
print("Updated Dictionary:")
print(student_scores)

Output:

Student Scores Dictionary:
{'Alice': 85, 'Bob': 92, 'Charlie': 78}

Score for Alice:
85

Updated Dictionary:
{'Alice': 85, 'Bob': 92, 'Charlie': 78, 'David': 88}

3.Tuples

Tuples in Python are a sequence type that, once created, cannot be altered. This immutability makes them ideal for data that should not change, helping ensure consistency throughout your code. Like lists, tuples maintain the order of their elements, so you can rely on indexing to access specific items or use slicing to retrieve subsets of data. In addition to being ordered and immutable, tuples can sometimes be slightly faster than lists for certain operations, thanks to their fixed nature.

You can create a tuple by separating values with commas, optionally enclosed in parentheses. Tuples can hold any type of data, including numbers, strings, and other tuples.

Example:

# Example 1: Creating a tuple with multiple data types
my_tuple = (42, 'Hello', 3.14, False)
print("Tuple with mixed data types:")
print(my_tuple)

# Example 2: Tuple without parentheses
another_tuple = 10, 20, 30
print("\nTuple without parentheses:")
print(another_tuple)

# Example 3: Tuple from a list
sample_list = [1, 2, 3]
tuple_from_list = tuple(sample_list)
print("\nTuple created from a list:")
print(tuple_from_list)

# Example 4: Single-element tuple
single_element = (5,)
print("\nSingle-element tuple (note the comma):")
print(single_element)

# Accessing Tuple Elements
print("\nAccessing first element:")
print(my_tuple[0])

print("\nAccessing last element:")
print(my_tuple[-1])

Output:

Tuple with the use of String: 
('Geeks', 'For')

Tuple using List: 
(1, 2, 4, 5, 6)

First element of tuple:
1

Last element of tuple:
6

Third last element of tuple:
4

4. Set

A Python set is an unordered collection of unique items that is mutable—meaning you can add or remove elements after its creation. Sets are ideal for membership testing and automatically eliminating duplicate entries. Internally, sets use a hash table, which allows operations like insertion, deletion, and lookup to typically run in constant time (O(1)).

In CPython, sets are implemented using a dictionary-like structure with dummy values, ensuring that each element is stored uniquely while efficiently handling hash collisions. This makes sets particularly useful for scenarios where you need to enforce uniqueness or perform rapid set operations such as union, intersection, and difference.

Example:

# Creating a set with mixed data types (numbers and strings)
mixed_set = set([1, 2, 'Cypher', 4, 'For', 6, 'Cypher'])
print("\nSet with Mixed Values:")
print(mixed_set)

# Iterating through the set elements
print("\nElements in the set:")
for element in mixed_set:
    print(element, end=" ")
print()

# Checking if 'Cypher' is present in the set
print("\nIs 'Cypher' in the set?")
print('Cypher' in mixed_set)

Output:

Set with Mixed Values:
{1, 2, 4, 6, 'For', 'Cypher'}

Elements in the set:
1 2 4 6 For Cypher 

Is 'Cypher' in the set?
True

5.Frozen Sets

A frozenset in Python is an immutable version of a set. Once created, its elements cannot be changed, and any operations return a new frozenset without altering the original. If no argument is provided, it creates an empty frozenset.

Example:

# Creating a mutable set of numbers
mutable_numbers = {10, 20, 30, 40}
print("Mutable Set:")
print(mutable_numbers)

# Creating an immutable frozenset with a different collection of numbers
immutable_numbers = frozenset([15, 25, 35, 45, 55])
print("\nImmutable Frozenset:")
print(immutable_numbers)

# Uncommenting the line below would result in an error because frozensets cannot be modified
# immutable_numbers.add(65)

Output:

Mutable Set:
{40, 10, 20, 30}

Immutable Frozenset:
frozenset({35, 45, 15, 55, 25})

6.String

Python strings are immutable sequences of Unicode characters (stored as arrays of bytes). This means that any modification creates a new string. Additionally, Python doesn’t have a separate character type—a single character is just a string of length 1.

Example:

   
# Demonstrating string immutability and characteristics

# Original string
original_string = "Hello, Python!"
print("Original String:")
print(original_string)

# Printing First character 
print("\nFirst character of String is: ") 
print(original_string[0])  

# Attempt to modify the string by replacing a substring.
# Since strings are immutable, this operation creates a new string.
modified_string = original_string.replace("Python", "World")
print("\nModified String (new copy):")
print(modified_string)

# The original string remains unchanged
print("\nOriginal String remains unchanged:")
print(original_string)

# A single character in Python is just a string of length 1
single_character = "A"
print("\nSingle Character (string of length 1):")
print(single_character)

Output:

Original String:
Hello, Python!

First character of String is:
H

Modified String (new copy):
Hello, World!

Original String remains unchanged:
Hello, Python!

Single Character (string of length 1):
A

7.Bytearray

A Python bytearray is a mutable sequence of numbers, where each number represents a byte and must be between 0 and 255. Unlike regular bytes objects, bytearrays can be modified after creation, making them ideal for tasks that require dynamic manipulation of binary data.

Example:

   
# Creating a bytearray from a list of integers (each must be between 0 and 255)
a = bytearray([100, 150, 200, 250])
print("Original Bytearray:")
print(a)

# Accessing elements
print("\nAccessing Elements:", a[1])

# Modifying elements 
a[1] = 3
print("\nAfter Modifying:")
print(a)

# Appending elements
a.append(30)
print("\nAfter Adding Elements:")
print(a[4])

# Note: Attempting to assign a value outside the allowed range (0 <= x < 256) would raise a ValueError.
# For example, uncommenting the following line would cause an error:
#a[1] = 300

# Attempting to assign a value outside the allowed range (0 <= x < 256) would raise a ValueError.
# Uncommenting the following line will result in an error:
# mutable_bytes[1] = 300

Output:

Original Bytearray:
bytearray(b'd\x96\xc8\xfa')

Accessing Elements: 150

After Modifying:
bytearray(b'd\x03\xc8\xfa')

After Adding Elements:
30

Till now, we have studied all the data structures built into core Python. Now, let’s dive deeper and explore the collections module, which provides advanced container types. These containers offer additional features and enhanced functionality, making them useful in many cases beyond what the basic data structures provide.

Collections Module

Python’s collections module enhances the functionality of the built-in data types. It offers a variety of specialized container types that provide additional features and improved performance compared to the basic structures.

8.Counters

A Counter is a dictionary subclass designed to count how often each element appears in an iterable. It stores elements as keys and their frequencies as values, much like a bag or multiset in other languages.

Example:

   
        
from collections import Counter

# Example: Counting occurrences of each fruit in a list
fruits = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']

# Create a Counter object to count the frequency of each fruit
fruit_counter = Counter(fruits)

print("Fruit Frequency:")
print(fruit_counter)

# Expected output:
# Fruit Frequency:
# Counter({'apple': 3, 'banana': 2, 'orange': 1})

Output:

Fruit Frequency:
Counter({'apple': 3, 'banana': 2, 'orange': 1})

9.OrderedDict

An OrderedDict is a subclass of the dictionary that preserves the order in which keys are inserted. This means that when you iterate over an OrderedDict, the items are returned in the order they were added.

Example:

   
        
from collections import OrderedDict

# Create an OrderedDict and insert some key-value pairs
od = OrderedDict()
od['apple'] = 1
od['banana'] = 2
od['cherry'] = 3

print("Original OrderedDict:")
for key, value in od.items():
    print(key, value)

# Removing an element (e.g., 'banana')
od.pop('banana')
print("\nAfter removing 'banana':")
for key, value in od.items():
    print(key, value)

# Re-inserting 'banana' to show that insertion order is preserved
od['banana'] = 2
print("\nAfter re-inserting 'banana':")
for key, value in od.items():
    print(key, value)

Output:

Original OrderedDict:
apple 1
banana 2
cherry 3

After removing 'banana':
apple 1
cherry 3

After re-inserting 'banana':
apple 1
cherry 3
banana 2

10.DefaultDict

A DefaultDict is a dictionary subclass that returns a default value for keys that don’t exist, avoiding a KeyError. When initializing a DefaultDict, you pass a callable (like int, list, etc.) that returns the default value whenever a missing key is accessed.

Example:

   
        
from collections import defaultdict

# Create a defaultdict with int as the default factory.
# This means missing keys will automatically have a default value of 0.
count_dict = defaultdict(int)

# A list of numbers with repetitions
numbers = [1, 2, 3, 4, 2, 4, 1, 2]

# Count the occurrences of each number
for num in numbers:
    count_dict[num] += 1

print(count_dict)
# Output: defaultdict(<class 'int'>, {1: 2, 2: 3, 3: 1, 4: 2})

Output:

defaultdict(<class 'int'>, {1: 2, 2: 3, 3: 1, 4: 2})

11.ChainMap

A ChainMap groups multiple dictionaries into a single, unified mapping. When you look up a key, it searches through each dictionary in the order they were provided and returns the first matching value it finds. This is useful for managing multiple contexts or layers of data without merging the dictionaries.

Example:

   
 from collections import ChainMap

# Define multiple dictionaries
dict1 = {'a': 1, 'b': 2}
dict2 = {'b': 3, 'c': 4}
dict3 = {'c': 5, 'd': 6}

# Create a ChainMap that groups the dictionaries.
# The order determines the priority when searching for keys.
chain = ChainMap(dict1, dict2, dict3)

print("ChainMap:")
print(chain)

# Accessing values:
# 'a' is only in dict1.
print("\nValue for 'a':", chain['a'])  # Output: 1

# 'b' exists in both dict1 and dict2.
# The value from dict1 is returned because it appears first.
print("Value for 'b':", chain['b'])  # Output: 2

# 'c' exists in both dict2 and dict3.
# The value from dict2 is returned because it is higher in the order.
print("Value for 'c':", chain['c'])  # Output: 4

# 'd' is only in dict3.
print("Value for 'd':", chain['d'])  # Output: 6

# Attempting to access a key that doesn't exist in any dictionary raises a KeyError.
try:
    print("Value for 'e':", chain['e'])
except KeyError:
    print("Key 'e' not found in any dictionary")
       

Output:

ChainMap:
ChainMap({'a': 1, 'b': 2}, {'b': 3, 'c': 4}, {'c': 5, 'd': 6})

Value for 'a': 1
Value for 'b': 2
Value for 'c': 4
Value for 'd': 6
Key 'e' not found in any dictionary

12.NamedTuple

A NamedTuple returns a tuple with named fields, allowing you to access elements by name instead of by their index. This makes your code more readable and maintainable when dealing with structured data. For example, instead of remembering that index 0 is the first name, you can directly refer to it as “fname” in a student tuple that includes first name, last name, and DOB.

Example:

   
 from collections import namedtuple

# Define the namedtuple with fields: fname, lname, and DOB.
Student = namedtuple('Student', ['fname', 'lname', 'DOB'])

# Create an instance of Student.
student1 = Student('Alice', 'Smith', '2001-04-15')

# Accessing elements by name.
print("First Name:", student1.fname)
print("Last Name:", student1.lname)
print("Date of Birth:", student1.DOB)

# Accessing elements by index.
print("\nAccessing using index:")
print("First Name:", student1[0])
print("Last Name:", student1[1])
print("Date of Birth:", student1[2])
       

Output:

First Name: Alice
Last Name: Smith
Date of Birth: 2001-04-15

Accessing using index:
First Name: Alice
Last Name: Smith
Date of Birth: 2001-04-15

13.Deque( Double Ended Queue )

A Deque (Double Ended Queue) is an optimized list-like container designed for fast appends and pops from both ends, achieving O(1) time complexity for these operations. It is implemented using a doubly linked list, which means that while operations at the ends are very efficient, accessing elements at random positions takes O(n) time.

Example:

   
 from collections import deque

# Create a deque with initial elements
dq = deque([1, 2, 3])
print("Initial deque:", dq)

# Append an element to the right end
dq.append(4)
print("After appending to right:", dq)

# Append an element to the left end
dq.appendleft(0)
print("After appending to left:", dq)

# Pop an element from the right end
right_elem = dq.pop()
print("After popping from right:", dq, "| Popped element:", right_elem)

# Pop an element from the left end
left_elem = dq.popleft()
print("After popping from left:", dq, "| Popped element:", left_elem)
       

Output:

Initial deque: deque([1, 2, 3])
After appending to right: deque([1, 2, 3, 4])
After appending to left: deque([0, 1, 2, 3, 4])
After popping from right: deque([0, 1, 2, 3]) | Popped element: 4
After popping from left: deque([1, 2, 3]) | Popped element: 0

14.UserDict

A UserDict is a dictionary-like container that wraps around standard dictionaries. It serves as a base class for creating custom dictionaries with additional or modified behavior, allowing you to tailor dictionary functionalities without altering the built-in type.

Example:

   
        
from collections import UserDict

# Creating a custom dictionary that disallows any deletion
class NoDeletionDict(UserDict):
    
    # Overriding __del__ to block deletion of the dictionary
    def __del__(self):
        raise RuntimeError("Deletion is not allowed in this dictionary")
        
    # Overriding pop to prevent removing an element
    def pop(self, key, default=None):
        raise RuntimeError("Deletion is not allowed in this dictionary")
        
    # Overriding popitem to prevent removing any item
    def popitem(self):
        raise RuntimeError("Deletion is not allowed in this dictionary")
    
# Example usage
data = NoDeletionDict({'x': 10, 'y': 20, 'z': 30})

print("Custom Dictionary:")
print(data)

# The following line, if uncommented, would raise a RuntimeError
# data.pop('x')

Output:

Custom Dictionary:
{'x': 10, 'y': 20, 'z': 30}
ERROR!
Exception ignored in: 
Traceback (most recent call last):
  File "", line 8, in __del__
RuntimeError: Deletion is not allowed in this dictionary

15.UserList

A UserList is a list-like container that wraps around standard list objects, allowing you to create custom lists with added or modified behavior without changing the built-in list type.

Example:

   
from collections import UserList

# Custom list class that disallows deletion operations
class MyList(UserList):
    # Override remove to prevent deletion by value
    def remove(self, value=None):
        raise RuntimeError("Deletion not allowed")
    
    # Override pop to prevent deletion by index
    def pop(self, index=None):
        raise RuntimeError("Deletion not allowed")

# Creating an instance of MyList with some initial elements
my_list = MyList([1, 2, 3, 4])

print("Original List:")
print(my_list)

# Appending a new element (this is allowed)
my_list.append(5)
print("\nAfter Insertion:")
print(my_list)

# Attempting to remove an element will raise an error
try:
    my_list.remove(3)
except RuntimeError as e:
    print("\nError on deletion:", e)

# Similarly, attempting to pop an element will also raise an error
try:
    my_list.pop()
except RuntimeError as e:
    print("Error on deletion using pop:", e)
        

Output:

Original List:
[1, 2, 3, 4]

After Insertion:
[1, 2, 3, 4, 5]

Error on deletion: Deletion not allowed
Error on deletion using pop: Deletion not allowed

16.UserString

A UserString is a string-like container that wraps around the built-in string type. It is useful for creating custom string classes with additional or modified behavior, much like UserDict and UserList do for dictionaries and lists.

Example:

   
  from collections import UserString

# Custom class for our website "Cypher Code"
class CypherString(UserString):
    
    # Function to append additional text to the string
    def append_text(self, s):
        self.data += s
        
    # Function to remove all occurrences of a substring from the string
    def remove_text(self, s):
        self.data = self.data.replace(s, "")

# Example usage for "Cypher Code"
cs = CypherString("Cypher")
print("Original String:", cs.data)

# Appending to the string
cs.append_text(" Code")
print("String After Appending:", cs.data)

# Removing a part of the string
cs.remove_text(" Code")
print("String After Removing ' Code':", cs.data)
      

Output:

Original String: Cypher
String After Appending: Cypher Code
String After Removing ' Code': Cypher

17.Linked List

A linked list is a linear data structure where elements, stored in nodes, are not placed in consecutive memory locations. Instead, each node contains a pointer (or reference) that links it to the next node, creating a chain-like structure.

Example:

   
        
# Define the Node class
class Node:
    def __init__(self, data):
        self.data = data  # Store the node's data
        self.next = None  # Initialize the next pointer to None

# Define the LinkedList class
class LinkedList:
    def __init__(self):
        self.head = None  # Start with an empty list

    # Function to print the linked list
    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# Create a simple linked list with 3 nodes
if __name__ == '__main__':
    # Instantiate the LinkedList
    ll = LinkedList()
    
    # Create three nodes
    ll.head = Node(1)
    second = Node(2)
    third = Node(3)
    
    # Link the nodes together: 1 -> 2 -> 3
    ll.head.next = second  # Link first node to second
    second.next = third    # Link second node to third

    # Traverse and print the linked list
    ll.print_list()

Output:

1
2
3

18. Link List Traversal

Linked list traversal involves starting at the head of the list and iterating through each node until the end is reached, printing the data stored in each node along the way. This process is typically implemented in a function like printList(), which can work with any linked list.

Example:

   
# Node class
class Node:
    def __init__(self, data):
        self.data = data  # Store data
        self.next = None  # Initialize next as None

# Linked List class
class LinkedList:
    def __init__(self):
        self.head = None  # Start with an empty list

    # Function to traverse the linked list and print each node's data
    def printList(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# Code execution starts here
if __name__ == '__main__':
    # Creating a linked list with three nodes
    linked_list = LinkedList()
    linked_list.head = Node(1)
    second = Node(2)
    third = Node(3)

    # Linking the nodes
    linked_list.head.next = second  # Link first node to second
    second.next = third             # Link second node to third

    # Traverse and print the linked list
    linked_list.printList()
        

Output:

1
2
3

19. Stack 

A stack is a linear data structure where all insertions and deletions occur at one end, called the top. It follows a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) approach, meaning that the most recently added item is the first one to be removed. The operations to add and remove items are commonly known as push and pop, respectively.

Example:

           
# Using a list to implement a stack

# Initialize an empty stack
stack = []

# Push operations (adding items to the stack)
stack.append("apple")
stack.append("banana")
stack.append("cherry")

print("Stack after push operations:")
print(stack)

# Pop operations (removing items from the stack in LIFO order)
print("\nItem popped from the stack:")
print(stack.pop())

print("\nStack after one pop:")
print(stack)

Output:

Stack after push operations:
['apple', 'banana', 'cherry']

Item popped from the stack:
cherry

Stack after one pop:
['apple', 'banana']

20. Queue

A queue is a linear data structure that operates on a First-In-First-Out (FIFO) basis. This means that items are added at the rear of the queue and removed from the front, ensuring that the item that has been in the queue the longest is processed first. This structure is commonly used in scenarios like customer service lines, where the first person to join the queue is the first to be served.

Example:

   
        
# Initializing a queue with integers
queue = []

# Adding elements to the queue
queue.append(10)
queue.append(20)
queue.append(30)

print("Initial queue:")
print(queue)

# Removing elements from the queue using pop(0) to simulate FIFO order
print("\nElements dequeued from queue:")
print(queue.pop(0))  # Removes 10
print(queue.pop(0))  # Removes 20
print(queue.pop(0))  # Removes 30

print("\nQueue after removing elements:")
print(queue)

# Uncommenting the following line would raise an IndexError
# because the queue is now empty.
# print(queue.pop(0))

Output:

Initial queue:
[10, 20, 30]

Elements dequeued from queue:
10
20
30

Queue after removing elements:
[]

21.Priority Queue

A Priority Queue is an abstract data structure in which each element is associated with a priority. Elements with higher priorities are removed before those with lower priorities. If two elements share the same priority, they are processed in the order they were added (following FIFO for those elements). A practical example is airline baggage handling, where items marked as “Business” or “First-class” are prioritized over others.

Example:

   
import heapq

class SupportTicketQueue:
    def __init__(self):
        self._heap = []
        self._order = 0  # This counter ensures FIFO order for items with equal priority

    def add_ticket(self, ticket, priority):
        # Lower numerical value means higher severity priority
        heapq.heappush(self._heap, (priority, self._order, ticket))
        self._order += 1

    def process_ticket(self):
        if self._heap:
            return heapq.heappop(self._heap)[-1]
        raise IndexError("No tickets to process")

# Example usage:
ticket_queue = SupportTicketQueue()

# Adding support tickets with severity priorities
ticket_queue.add_ticket("Ticket: System outage", 1)     # Highest priority
ticket_queue.add_ticket("Ticket: Payment issue", 2)
ticket_queue.add_ticket("Ticket: UI glitch", 3)
ticket_queue.add_ticket("Ticket: Database error", 1)      # Same high priority as system outage

print("Processing support tickets in order:")
while True:
    try:
        print(ticket_queue.process_ticket())
    except IndexError:
        break

Output:

Processing support tickets in order:
Ticket: System outage
Ticket: Database error
Ticket: Payment issue
Ticket: UI glitch

22. Heap queue

The heapq module in Python implements a heap queue algorithm, which is essentially a priority queue. In Python, heaps are implemented as min-heaps, meaning that the smallest element is always at the root (accessible at index 0). When you push or pop elements, the heap invariant is maintained, ensuring that operations like extracting or inserting the smallest element run in O(log n) time.

Example:

   
 import heapq

# Create a list of numbers
heap = [3, 1, 4, 1, 5, 9]
# Transform the list into a heap
heapq.heapify(heap)
print("Heap:", heap)
print("Smallest element (heap[0]):", heap[0])

# Insert a new element into the heap
heapq.heappush(heap, 2)
print("Heap after push:", heap)

# Remove the smallest element
smallest = heapq.heappop(heap)
print("Popped smallest element:", smallest)
print("Heap after pop:", heap)
       

Output:

Heap: [1, 1, 4, 3, 5, 9]
Smallest element (heap[0]): 1
Heap after push: [1, 1, 2, 3, 5, 9, 4]
Popped smallest element: 1
Heap after pop: [1, 3, 2, 4, 5, 9]

23. Binary Tree

A binary tree is a hierarchical data structure where each node can have at most two children, commonly referred to as the left and right child. The very top node is called the root, and any node without children is known as a leaf. Each node contains data along with two pointers (or references) that indicate its left and right children, establishing the tree’s structure. This simple yet powerful design is fundamental for various algorithms and operations in computer science.

I. Tree Traversal

It’s a set of techniques used to access and process nodes within tree data structures, such as binary trees, n-ary trees, and others.Tree traversal is the systematic process of visiting every node in a tree data structure exactly once. Unlike linear structures such as arrays or linked lists, trees allow multiple paths from any given node, which means there are several ways to traverse them.

The most common traversal methods are:

• • Depth-First Search (DFS):
    This strategy goes as deep as possible along one branch before backtracking. It includes three primary approaches:

    • Inorder (Left, Root, Right): Typically used with binary search trees to retrieve nodes in a sorted order.
    • Preorder (Root, Left, Right): Often used to create a copy of the tree or to generate prefix expressions.
    • Postorder (Left, Right, Root): Commonly applied when deleting trees or evaluating postfix expressions.

Example:

 
# Inorder Traversal (Left, Root, Right)
# Node class for the binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Create the binary tree
root = Node(1)          # Root node
root.left = Node(2)     # Left child of root
root.right = Node(3)    # Right child of root
root.left.left = Node(4)  # Left child of node 2
root.left.right = Node(5) # Right child of node 2


def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=' ')
        inorder(root.right)

# Preorder Traversal (Root, Left, Right)
def preorder(root):
    if root:
        print(root.data, end=' ')
        preorder(root.left)
        preorder(root.right)

# Postorder Traversal (Left, Right, Root)
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=' ')

print("\nDFS Traversals:")
print("Inorder (Left, Root, Right):")
inorder(root)  # Expected output: 4 2 5 1 3
print("\nPreorder (Root, Left, Right):")
preorder(root)  # Expected output: 1 2 4 5 3
print("\nPostorder (Left, Right, Root):")
postorder(root)  # Expected output: 4 5 2 3 1
print()

Output:

DFS Traversals:
Inorder (Left, Root, Right):
4 2 5 1 3 
Preorder (Root, Left, Right):
1 2 4 5 3 
Postorder (Left, Right, Root):
4 5 2 3 1 

• Breadth-First Search (BFS) or Level Order Traversal:
  This method visits nodes level by level, starting at the root and progressing to the next level only after all nodes at the current level have been processed.

  Example:

           
  # Inorder Traversal (Left, Root, Right)
  # Node class for the binary tree
  class Node:
      def __init__(self, data):
          self.data = data
          self.left = None
          self.right = None
  
  # Create the binary tree
  root = Node(1)          # Root node
  root.left = Node(2)     # Left child of root
  root.right = Node(3)    # Right child of root
  root.left.left = Node(4)  # Left child of node 2
  root.left.right = Node(5) # Right child of node 2
  
  
  from collections import deque
  
  def level_order(root):
      if not root:
          return
      queue = deque([root])
      while queue:
          node = queue.popleft()
          print(node.data, end=' ')
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)
  
  print("BFS (Level Order) Traversal:")
  level_order(root)  # Expected output: 1 2 3 4 5
  print()
  

  Output:

  BFS (Level Order) Traversal:
  1 2 3 4 5 
  

Other specialized traversal methods, such as boundary and diagonal traversals, are used for more specific applications like visualizing the outer structure of a tree or computing diagonal sums.

Each traversal technique serves different purposes, making tree traversal a versatile tool in data structure manipulation and problem solving.

24. Graph

A graph is a non-linear data structure made up of a set of nodes (or vertices) and the connections between them, called edges. In a graph, each edge links a pair of nodes, representing relationships or connections. More formally, a graph can be defined as a finite set of vertices along with a set of edges, where each edge connects two vertices.

For example, consider a graph with the vertex set V = {0, 1, 2, 3, 4} and the edge set E = {01, 12, 23, 34, 04, 14, 13}.

Graphs are commonly represented in one of two ways:

• Adjacency Matrix
• Adjacency List

Example:

          
# Define a graph using a dictionary (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Print the graph's adjacency list
for vertex, edges in graph.items():
    print(f"{vertex}: {edges}")

Output:

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'F']
D: ['B']
E: ['B', 'F']
F: ['C', 'E']

I. Adjacency Matrix

An adjacency matrix is a two-dimensional array with dimensions N x N, where N is the number of vertices in the graph. Let the matrix be denoted as graphMatrix[][]. In an unweighted graph, if graphMatrix[i][j] = 1, it signifies that there is an edge from vertex i to vertex j. For undirected graphs, the matrix is symmetric since every edge is bidirectional. In the case of weighted graphs, if graphMatrix[i][j] = w, it indicates that there is an edge between vertex i and vertex j with weight w.

Example:

# Number of vertices in the graph (we have 3 vertices: 0, 1, and 2)
N = 3

# Initialize a 3x3 matrix with all zeros.
# Each index [i][j] will represent if there's a connection between vertex i and vertex j.
graphMatrix = [[0 for _ in range(N)] for _ in range(N)]

# Add an edge between vertex 0 and vertex 1.
# This means vertex 0 is connected to vertex 1.
graphMatrix[0][1] = 1
graphMatrix[1][0] = 1  # Because the graph is undirected, the connection is two-way.

# Add an edge between vertex 1 and vertex 2.
# This means vertex 1 is connected to vertex 2.
graphMatrix[1][2] = 1
graphMatrix[2][1] = 1  # Again, the graph is undirected.

# Print the adjacency matrix

print("Adjacency Matrix for the Graph:")
for row in graphMatrix:
print(row)
# The element at [0][1] is 1, meaning there's an edge between vertex 0 and vertex 1. # The element at [1][2] is 1, meaning there's an edge between vertex 1 and vertex 2.

Output:

Adjacency Matrix for the Graph:
[0, 1, 0]
[1, 0, 1]
[0, 1, 0]

II. Adjacency List

An adjacency list represents a graph using an array (or list) where each element corresponds to a vertex. Let’s call this array neighbors. The size of neighbors is equal to the number of vertices in the graph. Each entry neighbors[i]contains a list of vertices that are adjacent to vertex i. For weighted graphs, each list can include pairs where each pair consists of a neighboring vertex and the weight of the edge connecting them. Below is an example of the adjacency list representation for the graph mentioned earlier.

Example:

   
# Class representing a node in the adjacency list
class ListNode:
    def __init__(self, data):
        self.vertex = data  # This can be a character like 'A'
        self.next = None

# Class representing the graph using an adjacency list
class Graph:
    def __init__(self, vertices):
        # vertices is a list of vertex labels
        self.vertices = vertices  
        self.num_vertices = len(vertices)
        # Create a mapping from vertex label to its index for convenience
        self.vertex_to_index = {vertex: i for i, vertex in enumerate(vertices)}
        # Initialize an array (list) for adjacency lists for each vertex
        self.adj_list = [None] * self.num_vertices

    def add_edge(self, src, dest):
        # Convert vertex labels to indices
        src_index = self.vertex_to_index[src]
        dest_index = self.vertex_to_index[dest]
        
        # Add an edge from src to dest (for undirected graphs, add both ways)
        node = ListNode(dest)
        node.next = self.adj_list[src_index]
        self.adj_list[src_index] = node

        # Add edge from dest to src
        node = ListNode(src)
        node.next = self.adj_list[dest_index]
        self.adj_list[dest_index] = node

    def print_graph(self):
        for i, vertex in enumerate(self.vertices):
            print(f"Adjacency list of vertex {vertex}:", end=" head")
            temp = self.adj_list[i]
            while temp:
                print(f" -> {temp.vertex}", end="")
                temp = temp.next
            print()

# Driver code
if __name__ == "__main__":
    # Define vertices as characters
    vertices = ['A', 'B', 'C', 'D']
    g = Graph(vertices)
    
    # Adding edges to the graph
    g.add_edge('A', 'B')
    g.add_edge('A', 'C')
    g.add_edge('B', 'D')
    g.add_edge('C', 'D')
    
    # Print the adjacency list representation of the graph
    g.print_graph()

Output:

Adjacency list of vertex A: head -> C -> B
Adjacency list of vertex B: head -> D -> A
Adjacency list of vertex C: head -> D -> A
Adjacency list of vertex D: head -> C -> B

A.Graph Traversal

Graph traversal is the process of systematically visiting every vertex and edge in a graph. Since graphs can have cycles and may not be connected like trees, specialized algorithms are used to ensure that all parts of the graph are explored without getting stuck in loops. The most common traversal methods are:

• Depth-First Search (DFS):
  This method explores as far as possible along one branch before backtracking, which is useful for exploring complex or deeply nested graph structures.

  The dfs function starts at a given node, prints it, marks it as visited, and then recursively visits each of its neighbors. This process continues until all nodes reachable from the starting node have been visited. 

• Breadth-First Search (BFS):
  This technique visits all the neighbors of a vertex before moving to the next level, making it ideal for finding the shortest path in unweighted graphs.

  The bfs function starts at a given node, uses a queue (deque) to explore each neighbor level by level, prints the node, marks it as visited, and enqueues all its unvisited neighbors. This ensures nodes are processed in the order they are discovered

   

These traversal methods are fundamental in tasks such as searching for specific nodes, finding connected components, pathfinding, and analyzing the overall structure of the graph.

Example:

   
# Define the graph as a dictionary (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# Depth-First Search (DFS) - using recursion
def dfs(node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor, visited)
            
print("DFS Traversal:")
dfs('A')  # Starting from node 'A'
print("\n")

# Breadth-First Search (BFS) - using a queue
from collections import deque

def bfs(start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

print("BFS Traversal:")
bfs('A')  # Starting from node 'A'
print()

Output:

DFS Traversal:
A B D E F C 

BFS Traversal:
A B C D E F