| Attribute | Details |
|---|---|
| Name | Harsh Dev Jha |
| Roll No. | 2501010168 |
| Course | Btech CSE Core |
| Section | A |
A node-based binary tree data structure where each node has at most two child nodes, with left children containing values less than the parent and right children containing values greater than the parent.
- Operations Supported:
insert,search,delete, andinordertraversal. - Location:
BST/bst.py
A directed, weighted graph data structure implementation optimized for sparse graph operations.
- Features: Breadth-First Search (BFS) and Depth-First Search (DFS) traversals.
- Location:
Graph/graph.py
Dedicated script demonstrating purely the logic for BFS and DFS graph search algorithms.
- Location:
BFS_DFS/traversals.py
A robust dictionary-like structure using a custom hashing algorithm.
- Operations Supported:
insert,retrieve,delete. - Collision Strategy: Separate Chaining (resolves collisions by storing lists of key-value pairs at each hash index).
- Location:
HashTable/hash_table.py
DS_Assign_4/
├── BFS_DFS/
│ └── traversals.py
├── BST/
│ └── bst.py
├── Graph/
│ └── graph.py
└── HashTable/
└── hash_table.py
To test any of the data structures, run the respective Python script from the root directory. Below are the execution commands and their expected outputs.
1. Binary Search Tree (BST) (Click to expand)
python BST/bst.pyExpected Output:
BST inorder: [20, 30, 40, 50, 60, 70, 80]
After delete 20 inorder: [30, 40, 50, 60, 70, 80]
Search 60 exists: True
2. Graph (BFS/DFS) (Click to expand)
python Graph/graph.pyExpected Output:
Graph BFS from A: ['A', 'B', 'C', 'D', 'E']
Graph DFS from A: ['A', 'B', 'D', 'E', 'C']
3. Traversals (Standalone Demo) (Click to expand)
python BFS_DFS/traversals.pyExpected Output:
BFS: ['A', 'B', 'C', 'D']
DFS: ['A', 'B', 'D', 'C']
4. Hash Table (Click to expand)
python HashTable/hash_table.pyExpected Output:
Get 6: six
Delete 1: True
Get 1: None
0: []
1: [[6, 'six'], [11, 'eleven']]
2: []
3: []
4: []
- Space Complexity of Graph: By utilizing an adjacency list, the space complexity is kept at
O(V + E)(Vertices + Edges), making it highly efficient compared to adjacency matrices (O(V^2)), especially for sparse graphs. - Traversal Mechanics:
- BFS leverages a Queue (FIFO) to explore nodes level-by-level.
- DFS uses a Stack (LIFO, via recursion) to explore as deep as possible before backtracking.
- Hash Collision Handling: Separate chaining prevents data loss during hash collisions. If two keys hash to the same bucket index
k, they are both appended to a linked structure (a Python list here) at indexk. This ensures deterministic retrieval atO(1)average time complexity.