# Data Structures and Algorithms

Based on CS-201, Data Structures, KTU curriculum.

To run locally, fork this repository and clone it.

# Table of contents

#### 1) Application of Arrays

#### 2) Linked Lists

#### 3) Stacks, Queues and Heaps

#### 4) Hashing Algorithms

#### 5) Sorting Algorithms

#### 6) Trees

#### 7) Graphs

## 1) Application of Arrays

### Basics

- Sparse matrix Addition
- Sparse matrix multilplication
- Polynomial addition
- Polynomial multiplication

## 2) Linked Lists

### Basics

- Insert element at head
- Insert element at the tail
- Insert element at any position
- Count number of nodes
- Search for an element
- Delete first element
- Delete last element
- Delete an element at a given position
- Implement Circular linked list
- Implement Doubly linked list

### Easy

- Find minimum and maximum value
- Reverse a linked list
- Swap any two adjacent nodes
- Print middle node
- Swap head and tail
- Count number of nodes in circular linked lists
- Count even and odd nodes
- Concatenate two linked lists
- Swap first half with second half
- Find predecessor and successor nodes
- Check if linked list is circular
- Check if length is odd or even
- Delete alternate Nodes

### Medium

- Insert into sorted linked list
- Sort a linked list - MergeSort, BubbleSort, SelectionSort, InsertionSort
- Remove duplicates from linked list
- Remove all occurences of a given element
- Copy common elements into third linked list
- Split into 3 linked list based on value
- Split into odd and even linked list
- Check if a linked list forms a palindrome
- Find distance between two given nodes in a circular linked list
- Find union of 2 linked lists

### Hard

- Reverse only second half of linked list
- Merge two sorted linked lists in-place
- Rotate a linked list by k places

### Miscellaneous

## 3) Stacks, Queues and Heaps

### Basics

- Implement stack using array
- Implement stack using linked list
- Implement queue using array
- Implement queue using linked list
- Implement circular queue
- Implement Deque
- Build max Heap from array (naive method)
- Build min Heap from array (naive method)
- Build max Heap from array using Heapify
- Build min Heap from array using Heapify

### Easy

- Reverse a number using stack
- Check for palindrome using stack
- Check for valid parentheses
- Convert infix expression to postfix
- Evaluate postfix expression
- Evaluate prefix expression
- Reverse elements a queue using stack

### Medium

- Implement queue using two stacks
- Implement stack using two queues
- Implement priority queue - Using Array 1, Using Array 2 , Using LinkedList 1, Using LinkedList 2, Using Heap(simple), Using Heap(advanced)

## 4) Hashing Algorithms

### Basics

- Insert set of keys into a hash table of given size using division method and linear probing.
- Store each words of a natural language text in a hash table of given size using the mod function and perform search.

## 5) Sorting Algorithms

### Basics

- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort

### Miscellaneous

- Randomized quick sort
- Counting sort

## 6) Trees

### Basics

- Linked representation and Sequential representation of binary trees
- Preorder Traversal (Recursive and Iterative)
- Inorder Traversal (Recursive and Iterative)
- Postorder traversal (Recursive and Iterative)
- Level order Traversal
- Find height, number of nodes and number of vertices
- Implement Binary Search Tree (BST) and perform insertion, searching and deletion

### Easy

- Create linked representation of binary tree from sequential and vice versa
- Check if two trees are same
- Check if linked and sequential represented binary trees are same
- Find minimum and maximum in a BST
- Count and delete leaf nodes
- Find sum of leaf nodes
- Count degree of nodes
- print all elements in a given range in a BST

### Medium

- Print nodes at a given level
- Find all ancestors of a given node
- Find the sibling of a given node
- Check if a binary tree is a binary search tree
- Print nodes at each level and find their sum
- Find and remove maximum element in a BST
- Find and remove minimum element in a BST
- Check if there is a path sum
- Check if tree is Symmetric
- Find second largest element in a BST without using inorder array
- Find sum of all left leaves and right leaves
- Find kth smallest element in a BST

### Hard

- Delete all nodes in a given range
- Merge 2 binary trees
- Create binary tree when Preorder & Inorder given
- Create binary tree when Postorder & Inorder given

### Miscellaneous

- Invert a binary tree
- DFS Spanning tree
- BFS Spanning tree
- Minimum cost spanning tree (using Kruskal's Algorithm)

## 7) Graphs

### Basics

- Adjacency Matrix representation
- Adjacency List representation
- Depth First Search and Traversal - Recursive and Iterative
- Breadth First Search and Traversal