Find k’th smallest node in a BST
Given a BST and a positive number k, find the k’th smallest node in it.
Tag: Depth-first search
Determine whether a graph is Bipartite using DFS
Given a graph, determine if it is bipartite using DFS. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
Convert a binary tree to BST by maintaining its original structure
Convert a given binary tree into a BST (Binary Search Tree) by keeping its original structure intact.
Convert binary tree to Left-child right-sibling binary tree
Given a normal binary tree, convert it into a Left–child right–sibling (LC–RS) binary tree. Each node in the LC–RS binary tree has two pointers: one to the node’s left child and one to its next sibling in the original binary tree.
Print a two-dimensional view of a binary tree
Write an efficient algorithm to print the two-dimensional view of a binary tree.
Calculate the height of a binary tree with leaf nodes forming a circular doubly linked list
Write an algorithm to compute a binary tree’s height with leaf nodes forming a circular doubly linked list where the leaf node’s left and right pointers will act as a previous and next pointer of the circular doubly linked list, respectively.
Check if a graph is strongly connected or not using one DFS Traversal
Given a directed graph, check if it is strongly connected or not. A directed graph is said to be strongly connected if every vertex is reachable from every other vertex.
Check if a binary tree is height-balanced or not
Given a binary tree, write an efficient algorithm to check if a tree is height-balanced or not. In a height-balanced tree, the absolute difference between the height of the left and right subtree for every node is 0 or 1.
Find first `k` maximum occurring words in a given set of strings
Given a huge set of words with duplicates present and a positive integer k, find the first k–maximum occurring words in it.
Lexicographic sorting of a given set of keys
Lexicographic sorting: Given a set of strings, print them in lexicographic order (dictionary/alphabetical order).
Find the maximum occurring word in a given set of strings
Given a huge set of words with duplicates present, find the maximum occurring word in it. If two words have the same count, return any one of them.
Generate a list of possible words from a character matrix
Given an M × N boggle board, find a list of all possible words that can be formed by a sequence of adjacent characters on the board.