Topics

• Linked List
• Stack
• Queue
• Binary Tree
• Binary Search Tree
• Heap
• Hashing
• Graph
• Advanced Data Structure
• Array
• Matrix
• Misc

Linked List

Singly Linked List:

• Introduction to Linked List
• Linked List vs Array
• Linked List Insertion
• Linked List Deletion
• A Programmer’s approach of looking at Array vs. Linked List
• Find Length of a Linked List (Iterative and Recursive)
• Search an element in a Linked List (Iterative and Recursive)
• How to write C functions that modify head pointer of a Linked List?
• Write a function to get Nth node in a Linked List
• Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
• Print the middle of a given linked list
• Nth node from the end of a Linked List
• Write a function to delete a Linked List
• Write a function that counts the number of times a given int occurs in a Linked List
• Reverse a linked list
• Detect loop in a linked list
• Function to check if a singly linked list is palindrome
• Given a linked list which is sorted, how will you insert in sorted way
• Intersection point of two Linked Lists.
• Recursive function to print reverse of a Linked List
• Remove duplicates from a sorted linked list
• Remove duplicates from an unsorted linked list
• Pairwise swap elements of a given linked list
• Practice questions for Linked List and Recursion
• Move last element to front of a given Linked List
• Intersection of two Sorted Linked Lists
• Delete alternate nodes of a Linked List
• Alternating split of a given Singly Linked List
• Merge two sorted linked lists
• Identical Linked Lists
• Merge Sort for Linked Lists
• Reverse a Linked List in groups of given size
• Reverse alternate K nodes in a Singly Linked List
• Delete nodes which have a greater value on right side
• Segregate even and odd nodes in a Linked List
• Detect and Remove Loop in a Linked List
• Add two numbers represented by linked lists | Set 1
• Delete a given node in Linked List under given constraints
• Union and Intersection of two Linked Lists
• Find a triplet from three linked lists with sum equal to a given number
• Rotate a Linked List
• Flattening a Linked List
• Add two numbers represented by linked lists | Set 2
• Sort a linked list of 0s, 1s and 2s
• Flatten a multilevel linked list
• Delete N nodes after M nodes of a linked list
• QuickSort on Singly Linked List
• Merge a linked list into another linked list at alternate positions
• Pairwise swap elements of a given linked list by changing links
• Given a linked list of line segments, remove middle points
• Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
• Can we reverse a linked list in less than O(n)?
• Clone a linked list with next and random pointer | Set 2
• Insertion Sort for Singly Linked List
• Point to next higher value node in a linked list with an arbitrary pointer

Circular Linked List:

• Circular Linked List Introduction and Applications,
• Circular Linked List Traversal
• Split a Circular Linked List into two halves
• Sorted insert for circular linked list

Doubly Linked List:

• Doubly Linked List Introduction and Insertion
• Delete a node in a Doubly Linked List
• Reverse a Doubly Linked List
• The Great Tree-List Recursion Problem.
• Copy a linked list with next and arbit pointer
• QuickSort on Doubly Linked List
• Swap Kth node from beginning with Kth node from end in a Linked List

Quiz on Linked List

Stack

• Introduction to Stack
• Infix to Postfix Conversion using Stack
• Evaluation of Postfix Expression
• Reverse a Sting using Stack
• Implement two stacks in an array
• Check for balanced parentheses in an expression
• Next Greater Element
• Reverse a stack using recursion
• The Stock Span Problem
• Design and Implement Special Stack Data Structure
• Implement Stack using Queues
• Design a stack with operations on middle element
• How to create mergable stack?
• How to efficiently implement k stacks in a single array?
• Iterative Tower of Hanoi

Quiz on Stack

Queue

• Queue Introduction and Array Implementation
• Linked List Implementation of Queue
• Applications of Queue Data Structure
• Priority Queue Introduction
• Deque (Introduction and Applications)
• Implement Queue using Stacks
• Check whether a given Binary Tree is Complete or not
• Find the largest multiple of 3
• Find the first circular tour that visits all petrol pumps
• Maximum of all subarrays of size k
• An I nteresting Method to Generate Binary Numbers from 1 to n
• How to efficiently implement k Queues in a single array?

Quiz on Queue

Binary Tree

• Binary Tree Introduction
• Handshaking Lemma and Interesting Tree Properties
• Binary Tree Properties
• Types of Binary Tree
• Applications of tree data structure
• Tree Traversals
• Threaded Binary Tree
• Size of a tree
• Determine if Two Trees are Identical
• Maximum Depth or Height of a Tree
• Write a C program to Delete a Tree.
• Write an Efficient C Function to Convert a Binary Tree into its Mirror Tree
• If you are given two traversal sequences, can you construct the binary tree?
• Given a binary tree, print out all of its root-to-leaf paths one per line.
• The Great Tree-List Recursion Problem.
• Level Order Tree Traversal
• Count leaf nodes in a binary tree
• Level order traversal in spiral form
• Check for Children Sum Property in a Binary Tree.
• Convert an arbitrary Binary Tree to a tree that holds Children Sum Property
• Diameter of a Binary Tree
• How to determine if a binary tree is height-balanced?
• Inorder Tree Traversal without Recursion
• Inorder Tree Traversal without recursion and without stack!
• Root to leaf path sum equal to a given number
• Construct Tree from given Inorder and Preorder traversals
• Given a binary tree, print all root-to-leaf paths
• Double Tree
• Maximum width of a binary tree
• Foldable Binary Trees
• Print nodes at k distance from root
• Get Level of a node in a Binary Tree
• Print Ancestors of a given node in Binary Tree
• Check if a given Binary Tree is SumTree
• Check if a binary tree is subtree of another binary tree
• Connect nodes at same level
• Connect nodes at same level using constant extra space
• Populate Inorder Successor for all nodes
• Convert a given tree to its Sum Tree
• Vertical Sum in a given Binary Tree
• Find the maximum sum leaf to root path in a Binary Tree
• Construct Special Binary Tree from given Inorder traversal
• Construct a special tree from given preorder traversal
• Check whether a given Binary Tree is Complete or not
• Boundary Traversal of binary tree
• Construct Full Binary Tree from given preorder and postorder traversals
• Iterative Preorder Traversal
• Morris traversal for Preorder
• Linked complete binary tree & its creation
• Ternary Search Tree
• Segment Tree | Set 1 (Sum of given range)
• Largest Independent Set Problem
• Iterative Postorder Traversal | Set 1 (Using Two Stacks)
• Iterative Postorder Traversal | Set 2 (Using One Stack)
• Reverse Level Order Traversal
• Construct Complete Binary Tree from its Linked List Representation
• Convert a given Binary Tree to Doubly Linked List | Set 1
• Tree Isomorphism Problem
• Find all possible interpretations of an array of digits
• Iterative Method to find Height of Binary Tree
• Custom Tree Problem
• Convert a given Binary Tree to Doubly Linked List | Set 2
• Print ancestors of a given binary tree node without recursion
• Difference between sums of odd level and even level nodes of a Binary Tree
• Print Postorder traversal from given Inorder and Preorder traversals
• Find depth of the deepest odd level leaf node
• Check if all leaves are at same level
• Print Left View of a Binary Tree
• Remove all nodes which don’t lie in any path with sum>= k
• Extract Leaves of a Binary Tree in a Doubly Linked List
• Deepest left leaf node in a binary tree
• Find next right node of a given key
• Sum of all the numbers that are formed from root to leaf paths
• Convert a given Binary Tree to Doubly Linked List | Set 3
• Lowest Common Ancestor in a Binary Tree | Set 1
• Find distance between two given keys of a Binary Tree
• Print all nodes that are at distance k from a leaf node
• Check if a given Binary Tree is height balanced like a Red-Black Tree,
• Print all nodes at distance k from a given node
• Print a Binary Tree in Vertical Order | Set 1
• Construct a tree from Inorder and Level order traversals
• Find the maximum path sum between two leaves of a binary tree
• Reverse alternate levels of a perfect binary tree
• Check if two nodes are cousins in a Binary Tree
• Check if a binary tree is subtree of another binary tree | Set 2
• Serialize and Deserialize a Binary Tree
• Print nodes between two given level numbers of a binary tree
• closest leaf in a Binary Tree
• Convert a Binary Tree to Threaded binary tree
• Print Nodes in Top View of Binary Tree
• Bottom View of a Binary Tree
• Perfect Binary Tree Specific Level Order Traversal
• Convert left-right representation of a bianry tree to down-right
• Print level order traversal line by line
• Minimum no. of iterations to pass information to all nodes in the tree
• Clone a Binary Tree with Random Pointers
• Given a binary tree, how do you remove all the half nodes?
• Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree)
• Check whether a binary tree is a full binary tree or not
• Find sum of all left leaves in a given Binary Tree
• Remove nodes on root to leaf paths of length < K
• Iterative Search for a key ‘x’ in Binary Tree
• Find maximum (or minimum) in Binary Tree

Quiz on Binary Tree

Quiz on Binary Tree Traversals

All articles on Tree

Binary Search Tree

• Search and Insert in BST
• Deletion from BST
• Minimum value in a Binary Search Tree
• Inorder predecessor and successor for a given key in BST
• Check if a binary tree is BST or not
• Lowest Common Ancestor in a Binary Search Tree.
• Sorted order printing of a given array that represents a BST
• Inorder Successor in Binary Search Tree
• Find k-th smallest element in BST (Order Statistics in BST)
• Print BST keys in the given range
• Sorted Array to Balanced BST
• Find the largest BST subtree in a given Binary Tree
• Check for Identical BSTs without building the trees
• Add all greater values to every node in a given BST
• Remove BST keys outside the given range
• Check if each internal node of a BST has exactly one child
• Find if there is a triplet in a Balanced BST that adds to zero
• Merge two BSTs with limited extra space
• Two nodes of a BST are swapped, correct the BST
• Construct BST from given preorder traversal | Set 1
• Construct BST from given preorder traversal | Set 2
• Floor and Ceil from a BST
• Convert a BST to a Binary Tree such that sum of all greater keys is added to every key
• Sorted Linked List to Balanced BST
• In-place conversion of Sorted DLL to Balanced BST
• Find a pair with given sum in a Balanced BST
• Total number of possible Binary Search Trees with n keys
• Merge Two Balanced Binary Search Trees
• Binary Tree to Binary Search Tree Conversion
• Transform a BST to greater sum tree
• Inorder predecessor and successor for a given key in BST
• K’th Largest Element in BST when modification to BST is not allowed
• How to handle duplicates in Binary Search Tree?

Quiz on Binary Search Trees

Quiz on Balanced Binary Search Trees

Heap

• Binary Heap
• Binomial Heap
• Heap Sort
• K’th Largest Element in an array
• Sort an almost sorted array/
• Sort an almost sorted array/
• Tournament Tree (Winner Tree) and Binary Heap

Hashing

• Hashing Introduction
• Print a Binary Tree in Vertical Order
• Find whether an array is subset of another array
• Union and Intersection of two Linked Lists
• Find a pair with given sum
• Check if a given array contains duplicate elements within k distance from each other
• Find Itinerary from a given list of tickets
• Find number of Employees Under every Employee

Quiz on Hashing

Graph

Introduction, DFS and BFS:

• Graph and its representations
• Breadth First Traversal for a Graph
• Depth First Traversal for a Graph
• Applications of Depth First Search
• Applications of Breadth First Traversal
• Detect Cycle in a Directed Graph
• Detect Cycle in a an Undirected Graph
• Detect cycle in an undirected graph
• Longest Path in a Directed Acyclic Graph
• Topological Sorting
• Check whether a given graph is Bipartite or not
• Snake and Ladder Problem
• Minimize Cash Flow among a given set of friends who have borrowed money from each other
• Boggle (Find all possible words in a board of characters)
• Assign directions to edges so that the directed graph remains acyclic

Minimum Spanning Tree:

• Prim’s Minimum Spanning Tree (MST))
• Applications of Minimum Spanning Tree Problem
• Prim’s MST for Adjacency List Representation
• Kruskal’s Minimum Spanning Tree Algorithm
• Boruvka’s algorithm for Minimum Spanning Tree

Shortest Paths:

• Dijkstra’s shortest path algorithm
• Dijkstra’s Algorithm for Adjacency List Representation
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson’s algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Some interesting shortest path questions,
• Shortest path with exactly k edges in a directed and weighted graph

Connectivity:

• Find if there is a path between two vertices in a directed graph
• Connectivity in a directed graph
• Articulation Points (or Cut Vertices) in a Graph
• Biconnected graph
• Bridges in a graph
• Eulerian path and circuit
• Fleury’s Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Transitive closure of a graph
• Find the number of islands
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Biconnected Components
• Check if a given graph is tree or not
• Karger’s algorithm for Minimum Cut 

Hard Problems:

• Graph Coloring (Introduction and Applications)
• Greedy Algorithm for Graph Coloring
• Travelling Salesman Problem (Naive and Dynamic Programming)
• Travelling Salesman Problem (Approximate using MST)
• Hamiltonian Cycle
• Vertex Cover Problem | Set 1 (Introduction and Approximate Algorithm)
• K Centers Problem | Set 1 (Greedy Approximate Algorithm)

Maximum Flow:

• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem

Quiz on Graph

Quiz on Graph Traversals

Quiz on Graph Shortest Paths

Quiz on Graph Minimum Spanning Tree

Advanced Data Structure

Advanced Lists:

• Memory efficient doubly linked list
• XOR Linked List – A Memory Efficient Doubly Linked List | Set 1
• XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
• Skip List | Set 1 (Introduction)
• Self Organizing List | Set 1 (Introduction)

Trie:

• Trie | (Insert and Search)
• Trie | (Delete)
• Longest prefix matching – A Trie based solution in Java
• Print unique rows in a given boolean matrix

• How to Implement Reverse DNS Look Up Cache?
• How to Implement Forward DNS Look Up Cache?

Suffix Array and Suffix Tree:

• Suffix Array Introduction
• Suffix Array nLogn Algorithm
• Suffix Tree Introduction
• Ukkonen’s Suffix Tree Construction – Part 1
• Ukkonen’s Suffix Tree Construction – Part 2
• Ukkonen’s Suffix Tree Construction – Part 3
• Ukkonen’s Suffix Tree Construction – Part 4,
• Ukkonen’s Suffix Tree Construction – Part 5
• Ukkonen’s Suffix Tree Construction – Part 6
• Generalized Suffix Tree
• Build Linear Time Suffix Array using Suffix Tree
• Substring Check
• Searching All Patterns
• Longest Repeated Substring,
• Longest Common Substring, Longest Palindromic Substring

AVL Tree:

• AVL Tree | Set 1 (Insertion)
• AVL Tree | Set 2 (Deletion)

• AVL with duplicate keys

Splay Tree:

• Splay Tree | Set 1 (Search)
• Splay Tree | Set 2 (Insert)

B Tree:

• B-Tree | Set 1 (Introduction)
• B-Tree | Set 2 (Insert)
• B-Tree | Set 3 (Delete)

Segment Tree:

• Segment Tree | Set 1 (Sum of given range)
• Segment Tree | Set 2 (Range Minimum Query)

Red-Black Tree:

• Red-Black Tree Introduction
• Red Black Tree Insertion.
• Red-Black Tree Deletion
• Program for Red Black Tree Insertion

Others:

• Ternary Search Tree
• Interval Tree
• Implement LRU Cache
• Sort numbers stored on different machines
• Find the k most frequent words from a file
• Given a sequence of words, print all anagrams together
• Tournament Tree (Winner Tree) and Binary Heap
• Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)
• Spaghetti Stack
• Data Structure for Dictionary and Spell Checker?
• KD Tree
• Binomial Heap
• KD Tree
• Binary Indexed Tree

Array

• Given an array A[] and a number x, check for pair in A[] with sum as x
• Majority Element
• Find the Number Occurring Odd Number of Times
• Largest Sum Contiguous Subarray
• Find the Missing Number
• Search an element in a sorted and pivoted array
• Merge an array of size n into another array of size m+n
• Median of two sorted arrays
• Write a program to reverse an array
• Program for array rotation
• Reversal algorithm for array rotation
• Block swap algorithm for array rotation
• Maximum sum such that no two elements are adjacent
• Leaders in an array
• Sort elements by frequency | Set 1
• Count Inversions in an array
• Two elements whose sum is closest to zero
• Find the smallest and second smallest element in an array
• Check for Majority Element in a sorted array
• Maximum and minimum of an array using minimum number of comparisons
• Segregate 0s and 1s in an array
• k largest(or smallest) elements in an array | added Min Heap method
• Maximum difference between two elements
• Union and Intersection of two sorted arrays
• Floor and Ceiling in a sorted array
• A Product Array Puzzle
• Segregate Even and Odd numbers
• Find the two repeating elements in a given array
• Sort an array of 0s, 1s and 2s
• Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
• Find duplicates in O(n) time and O(1) extra space
• Equilibrium index of an array
• Linked List vs Array
• Which sorting algorithm makes minimum number of memory writes?
• Turn an image by 90 degree
• Next Greater Element
• Check if array elements are consecutive | Added Method 3
• Find the smallest missing number
• Count the number of occurrences in a sorted array
• Interpolation search vs Binary search
• Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
• Maximum of all subarrays of size k (Added a O(n) method)
• Find whether an array is subset of another array | Added Method 3
• Find the minimum distance between two numbers
• Find the repeating and the missing | Added 3 new methods
• Median in a stream of integers (running integers)
• Find a Fixed Point in a given array
• Maximum Length Bitonic Subarray
• Find the maximum element in an array which is first increasing and then decreasing
• Count smaller elements on right side
• Minimum number of jumps to reach end
• Implement two stacks in an array
• Find subarray with given sum
• Dynamic Programming | Set 14 (Maximum Sum Increasing Subsequence)
• Longest Monotonically Increasing Subsequence Size (N log N)
• Find a triplet that sum to a given value
• Find the smallest positive number missing from an unsorted array
• Find the two numbers with odd occurrences in an unsorted array
• The Celebrity Problem
• Dynamic Programming | Set 15 (Longest Bitonic Subsequence)
• Find a sorted subsequence of size 3 in linear time
• Largest subarray with equal number of 0s and 1s
• Dynamic Programming | Set 18 (Partition problem)
• Maximum Product Subarray
• Find a pair with the given difference
• Replace every element with the next greatest
• Dynamic Programming | Set 20 (Maximum Length Chain of Pairs)
• Find four elements that sum to a given value | Set 1 (n^3 solution)
• Find four elements that sum to a given value | Set 2 ( O(n^2Logn) Solution)
• Sort a nearly sorted (or K sorted) array
• Maximum circular subarray sum
• Find the row with maximum number of 1s
• Median of two sorted arrays of different sizes
• Shuffle a given array
• Count the number of possible triangles
• Iterative Quick Sort
• Find the number of islands
• Construction of Longest Monotonically Increasing Subsequence (N log N)
• Find the first circular tour that visits all petrol pumps
• Arrange given numbers to form the biggest number
• Pancake sorting
• A Pancake Sorting Problem
• Tug of War
• Divide and Conquer | Set 3 (Maximum Subarray Sum)
• Counting Sort
• Merge Overlapping Intervals
• Find the maximum repeating number in O(n) time and O(1) extra space
• Stock Buy Sell to Maximize Profit
• Rearrange positive and negative numbers in O(n) time and O(1) extra space
• Sort elements by frequency | Set 2
• Find a peak element
• Print all possible combinations of r elements in a given array of size n
• Given an array of of size n and a number k, find all elements that appear more than n/k times
• Find the point where a monotonically increasing function becomes positive first time
• Find the Increasing subsequence of length three with maximum product
• Find the minimum element in a sorted and rotated array
• Stable Marriage Problem
• Merge k sorted arrays | Set 1
• Radix Sort
• Move all zeroes to end of array
• Find number of pairs such that x^y > y^x
• Count all distinct pairs with difference equal to k
• Find if there is a subarray with 0 sum
• Smallest subarray with sum greater than a given value
• Sort an array according to the order defined by another array
• Maximum Sum Path in Two Arrays
• Check if a given array contains duplicate elements within k distance from each other
• Sort an array in wave form
• K’th Smallest/Largest Element in Unsorted Array, K’th Smallest/Largest Element in Unsorted Array in Expected Linear Time,
• K’th Smallest/Largest Element in Unsorted Array in Worst Case Linear Time
• Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array
• Find the closest pair from two sorted arrays
• Given a sorted array and a number x, find the pair in array whose sum is closest to x
• Count 1’s in a sorted binary array
• Print All Distinct Elements of a given integer array
• Construct an array from its pair-sum array
• Find common elements in three sorted arrays
• Find the first repeating element in an array of integers
• Find the smallest positive integer value that cannot be represented as sum of any subset of a given array
• Rearrange an array such that ‘arr[j]’ becomes ‘i’ if ‘arr[i]’ is ‘j’
• Find position of an element in a sorted array of infinite numbers
• Can QuickSort be implemented in O(nLogn) worst case time complexity?
• Check if a given array contains duplicate elements within k distance from each other
• Find the element that appears once
• Replace every array element by multiplication of previous and next
• Check if any two intervals overlap among a given set of intervals
• Delete an element from array (Using two traversals and one traversal)
• Given a sorted array and a number x, find the pair in array whose sum is closest to x
• Find the largest pair sum in an unsorted array
• Online algorithm for checking palindrome in a stream
• Find Union and Intersection of two unsorted arrays
• Pythagorean Triplet in an array
• Maximum profit by buying and selling a share at most twice

Quiz on Array

Matrix

• Search in a row wise and column wise sorted matrix
• Print a given matrix in spiral form
• A Boolean Matrix Question
• Print unique rows in a given boolean matrix
• Maximum size square sub-matrix with all 1s
• Print unique rows in a given boolean matrix
• Inplace M x N size matrix transpose | Updated
• Print Matrix Diagonally
• Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
• Strassen’s Matrix Multiplication
• Create a matrix with alternating rectangles of O and X
• Find the row with maximum number of 1s
• Print all elements in sorted order from row and column wise sorted matrix
• Given an n x n square matrix, find sum of all sub-squares of size k x k
• Count number of islands where every island is row-wise and column-wise separated
• Find a common element in all rows of a given row-wise sorted matrix
• Given a matrix of ‘O’ and ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’

Misc

• Commonly Asked Data Structure Interview Questions | Set 1
• A data structure for n elements and O(1) operations

You can create a new Data Structure topic and discuss it with other geeks using Geeksforgeeks Q&A page. See already discussed Data Structure questions on forum.