Reverse a doubly linked list
In this post, we will see how to reverse a doubly linked list using iteration and recursion.
Tag: Recursive
Construct a full binary tree from a preorder and postorder sequence
A full binary tree is a tree in which every node has either 0 or 2 children. Write an efficient algorithm to construct a full binary tree from a given preorder and postorder sequence.
Find the number of ways to fill an `N × 4` matrix with `1 × 4` tiles
Given an n × 4 matrix where n is a positive number, find the number of ways to fill the matrix with 1 × 4 tiles.
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.
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.