Data Structures

Covering directly from labels, these are the main topics:


DS concepts
Link list
Double link list
Tree
BST

Arrays


Stack

• Stack ADT
• Stack implementation using arrays in C++
• Stack implementation using linked list
• Circular stack
• Circular stack in cpp
• Implement 3 stacks in 1 Array
• Some questions on Stack
•  Implement a Queue using two stacks
•  Sorting a Stack using push,pop,isEmpty and peek
• Reversing the stack "in-place" using recursion
•  Stack DS to implement constant time Minimum element lookup
• Implement a queue in which push_rear(), pop_front and get_min() are constant time operations

Queue

• Circular Queue
•  Implement a Queue using two stacks
• Implement a queue in which push_rear(), pop_front and get_min() are constant time operations

Linked List Problems
(Note : By linked list we mean is Singly Linked List)

• Link List Datastructure
• Basic Functions of the linked list - Add and Print
• Reverse a linked list
• Inorder successor 
• Binary Search on the linked list
• Palindrome in single linked list
• Intersection of 2 sorted list
• Median of linked list or a tree
• Adding 2 large numbers using reversal of numbers first
• Adding 2 large numbers without reversing them
• Finding a cycle in linked list
• Detecting a loop in the single linked list
• Deleting a middle element from the list
• Get middle of the linked list
• Find the Nth node from the end of the link list
• Copy a linked list
• Deleting duplicate nodes from the linked list

BST / Binary Search Tree

• What is BST or Binary Search tree?
• Implementing BST in C ( header file ) BST / Binary Search 
• Deleting a node 
• tree1.h fully updated 
• What is a Complete Binary Tree? 
• Given a binary tree,create the copy of the tree.
• Given a binary tree, count the number of nodes in the tree.
• Given a binary tree, find the maximum depth the number of nodes along the longest path from the root node down to the farthest leaf node.
• isBst–Whether the tree provided is BST or not
• Count trees–Given N nodes, how many structurally
• Write a code to find the minimum and maximum value in binary search tree
• Print the paths in binary search tree from root to leaves.
• Check whether binary tree are same or not?
• Get the mirror of Binary tree
• BST : Binary search tree with double tree
• Print the post order of binary search tree in cpp
• BT: How to check whether 2 trees are same or not?
• BST: How to check whether 2 trees are BST or NOT
• Construct a tree given its inorder and preorder
• Given an expression tree, calculate the expression
• Getting the size of Binary Search Tree (cpp)
• Create Copy of a tree (cpp) 

Traversal

• Print the post order traversal (recursive)
• Print the BST in increasing order…to put this in different way, it simply means to print in inorder traversal 
• Find Diameter of Binary Tree
• Duplicate removal in Binary Search Tree
• Morris Traversal - Inorder Tree Traversal without recursion and without stack
• Find nth largest value in a BST
• BST : Improving search by using sentinel
• Print binary search tree in increasing order
• Find the minimum data value find in Binary Search
• Compute Maximum depth of binary search tree in cpp 
• Print the binary tree in zigzag level order
• Construct a tree given its inorder and preorder traversal. Similarly construct tree for inorder and postorder traversal
• Given an expression tree, evaluate the expression and obtain the paranthesized form of expression.
•  Find the closest ancestor of two nodes in a tree 
• Threaded binary tree Algorithms
• DFS and BFS on tree.
• Iterative traversal (pre, post and inorder) of tree
• Binary search tree BST / Binary Search Tree
• Level order Traversal 
• BST:Return Nth Node in in-order traversal

Heap

• Introduction to Heap
• Binary Heap Introduction
• Binary Heap - Array Based implementation
• Min Heap - Removing the min element
• Heap - Inserting the element into a heap
• Heap sort
• Heap sort in java

Priority queue
Priority queue


HASHING

• Hash Tables

Bloom filter
Bloom filter

Graph Data Structure
What is a graph data-structure?
Cuts of graphs
Minimum cut problem
Graph Representations
Random Contraction Algorithm

Graph Search Algorithms
Graph Search Introduction
BFS - Breadth first search
BFS on tree
Application of BFS -

• Djikstra's algorithm for equal weight edge graph
• BFS and undirected graph connectivity

DFS (Depth first search) for graph

DFS - Depth First Search for tree

Application of DFS -

• Topological sorting
• Strongly Connected Components

Dijkstra's shortest path algorithm

Balanced BST
Introduction

Red Black Tree
Red Black Tree
Red Black Tree - Insertions
Red Black Tree - Deletions

AVL Tree
Introduction
Insertion of element
AVL Tree - Rotations
Deletion of element

Splay trees

Suffix Trees

Interval Search Tree

Skiplist

• Skiplists
• Skiplist vs Binary tree

Tries

1. Trie ADT
2. Implementing trie ADT in java
3. Inserting in trie
4. Searching in trie
5. Trie Operations Complexity

Rope

Resources and References