Pairwise swap adjacent nodes of a linked list
Given a linked list, pairwise swap its adjacent nodes. The swapping of data is not allowed, only links should be changed.
Tag: Recursive
Count subtrees in a BST whose nodes lie within a given range
Given a BST, count subtrees in it whose nodes lie within a given range.
Reverse a stack using recursion
Given a stack, recursively reverse it only using its abstract data type (ADT) standard operations, i.e., push(item), pop(), peek(), isEmpty(), size(), etc.
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.
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 total ways to reach the n’th stair from the bottom
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person can only climb either 1 or 2 or 3 stairs at a time.
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.
Construct a Cartesian tree from an inorder traversal
Write an efficient algorithm to construct a Cartesian tree from inorder traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has a smaller value than the node itself.
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.
Check if a linked list of strings is palindromic
Given a linked list of strings, check whether the concatenation of all values in the list together forms a palindrome. It is not permissible to construct a string out of the linked list nodes and check that string for palindrome.
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.