# Data Structure Tutorial

This section contains the **data structure tutorial** with the most common and most popular topics like Linked List, Stack, Queue, Tree, Graph etc.

**Data structure is logical or mathematical organization of data**; it describes how to store the data and access data from memory. Actually in our programming data stored in main memory(RAM) and To develop efficient software or firmware we need to care about memory. To efficiently manage we required **data structure**.

There are two different types of **data structure**:

**Linear Data Structure:**In linear data structure data elements stored in sequential manner. Stack, Queue and Linked List are the types of linear data structure.**Non Linear Data Structure:**In Non-Linear data structure data elements are not stored in the sequence manner. Tree and Graph are the type of non-linear data structure.

## Topics of Data Structure

List of **Data Structure Tutorial** topics...

## Basics

- Structured Programming, its Advantages and Disadvantages.
- Data Structure types and operations associated with them.
- Introduction of Data Structure.
- Linear, Binary & Interpolation search.

## Array

## Linked List

- Introduction to Linked List
- Single Linked list and its basic operations with traversing implementation
- Single linked list insertion
- Single linked list deletion
- Deleting a node from a linked list without head pointer
- Implement union and intersection of two sorted linked lists

## Stack

- Stack
- Implement of stack using array
- Implementation of Multi Stack in C
- Nesting of parentheses using stack
- Check for balanced parentheses by using Stacks (C++ program)
- Double Stack
- Implementation of Stack using two Queues

## Queue

- Linear Queue
- Circular Queue
- Double Ended Queue (DeQueue)
- Priority Queue
- Implementation of Queue using two Stacks

## Hashing

- Hashing Data Structure
- Hash functions and its characteristics
- Collisions in Hashing and Collision Resolution Techniques
- Hashing | Separate chaining for collision resolution
- Hashing | Open addressing for collision handling
- Hashing coding problems

## Tree

- Tree Data structure
- Introduction to Trees and its terminologies.
- Binary tree, Definition and its properties.
- Binary Search Tree (BST)
- Binary Tree representation (Sequential and Link).
- Traversal technique for Binary Tree.
- Insertion in Binary Search Tree (BST) | Set 1
- Insertion in a Binary Search Tree | Set 2
- Deletion in Binary Search Tree (BST) | Set 1
- Deletion in Binary Search Tree (BST) | Set 2
- Comparison between Hash Table and Binary Search Tree
- Construct BST from Given Preorder Traversal
- Construct a binary search tree from a sorted linked list
- Construct a binary search tree from a sorted 1-D array
- Convert given Binary Search Tree to a Greater Sum Tree
- Convert given Binary Search Tree to a Smaller Sum Tree
- Construct all possible BSTs with keys 1 to N
- Convert a Binary Search Tree into a min-heap
- Construct BST from level order traversal
- Convert an unbalanced BST to a balanced BST
- Check if the given array can represent Preorder Traversal of a Binary Search Tree
- Kth Minimum in a Binary Search Tree
- Kth Maximum in a Binary Search Tree
- Check if given sorted subsequence exits in the Binary Search Tree or Not
- Check if the Binary Search Tree contains a dead end
- Check if the given array can represent inorder traversal of a BST
- Check if two BSTs have same set of elements or not
- Largest Element in the BST less than or Equal to N
- Distance between two nodes in a BST
- Count Number of pairs from two different BSTs whose sum is equal to X
- Merge Two Binary Search Trees Set 1
- Merge two Binary Search Trees set 2 (limited space)
- Find the Minimum and Maximum node in a Binary Search Tree
- Find Height (Maximum Depth) of a Binary Search Tree (C++ program).
- Find the Number of Nodes in a Binary Search Tree (C++ program).
- Find the number of leaf nodes in a Binary Tree | Data Structure.
- Find whether two trees are structurally identical or not | Data Structure.
- AVL Tree, Left and right rotations.
- Introduction to B Tree and its operations
- Red Black Tree (Properties, Advantages, Inserting Nodes).
- Interval Tree in Data Structure.
- Threaded Binary Tree | Data Structure.
- Level Order Traversal on a Binary Tree | Data Structure.
- Segment Trees
- Construct a Binary Tree from Postorder and Inorder Traversal

## Graph

- Introduction to Graph in Data Structure
- Representation of a Graph in Data Structure
- Breath First Search (BFS) of a Graph
- Depth First Search (DFS) of a Graph
- Cycle Detection in an Undirected Graph
- Cycle Detection in a Directed Graph
- Prim's Minimum Spanning Tree
- Count all the possible path between two vertices
- Insertion and deletion of nodes and edges in a graph using adjacency list

## Disjoint Set ADT

## Sorting

## Heap

- Introduction to Heap Data Structure
- Rearrange a string so that no two adjacent characters have the same letter

**Data Structure programs using C/C++**

- Quick Sort in C++ with Algorithm, Example.
- Merge Sort in C++ with Example.
- Counting Sort with C++ Example.
- Implement shell sort using C++ program.
- Dijkstra’s Algorithm: Explanation and Implementation with C++ program.
- C++ print Postorder traversal from Preorder and Inorder traversal of a tree.
- Infix To Postfix Conversion Using Stack [with C program].
- Evaluation of Postfix Expressions Using Stack [with C program].
- Maximum Sum Helix path (using C++ program).
- Tower of Hanoi using recursion (C++ program).
- Find in-order Successor and Predecessor in a BST using C++ program.
- Implement in-order traversal using C++ program.
- Implement post-order traversal using C++ program.
- Implement pre-order traversal using C++ program.
- Find occurrence of each element in an array using simple method O(n^2) and hashing O(n) time.
- Check for balanced parentheses by using Stacks (C++ program)

**Competitive Questions**

**Misc.**

- Augmenting Data Structure.
- Tail Recursion and Tower of Hanoi using C.
- Asymptotic Notations.
- Hashing (Hash table, Hash functions and its characteristics).
- Hamiltonian Cycle in Data Structure.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions