Find all possible binary trees having the same inorder traversal
Given an inorder sequence of a binary tree, find all possible binary trees having that same inorder traversal.
Tag: Hard
Flatten a Linked List
Given a linked list that can grow in both horizontal and vertical directions (right and down), flatten it into a sorted singly linked list provided that each horizontal and vertical list is already sorted.
Find correct order of alphabets in a given dictionary of ancient origin
Given a dictionary of ancient origin where the words are arranged alphabetically, find the correct order of alphabets in the ancient language.
Build a Binary Search Tree from a postorder sequence
Given a distinct sequence of keys representing the postorder traversal of a binary search tree, construct a BST from it.
Build a Binary Search Tree from a preorder sequence
Given a distinct sequence of keys representing the preorder sequence of a binary search tree (BST), construct a BST from it.
Recursive solution to sort a stack
Given a stack, sort it using recursion. The use of any other data structures (like containers in STL or Collections in Java) is not allowed.
Ways to reach the bottom-right corner of a matrix with exactly `k` turns allowed
Given an M × N matrix, count the number of different ways to reach the bottom-right corner of a matrix from its top-left corner with exactly k turn allowed and using only the directions right and down.
Sort an array using Young tableau
In this post, we will see how to sort N^2 numbers in increasing order using an N × N Young tableau in O(N^3) time.
Young Tableau | Insert, Search, Extract-Min, Delete, Replace
An M × N Young tableau is an M × N matrix such that the entries of each row are sorted from left to right and the entries of each column are sorted from top to bottom. Some entries of a Young tableau may be infinity, which indicates an empty entry.
Box Stacking Problem
Given a set of rectangular 3D boxes (cuboids), create a stack of boxes as tall as possible and return the maximum height of the stacked boxes.
Link nodes present in each level of a binary tree in the form of a linked list
Given a binary tree, write an efficient algorithm to link nodes at the same level in the form of a linked list like structure.
Implementation of Treap Data Structure (Insert, Search, and Delete)
This post will implement a treap data structure, a combination of a binary search tree and a heap, and perform basic operations like insert, search, and delete on it.