Clone a binary tree with random pointers
Write an efficient code to clone a binary tree with each node containing an additional random pointer. The random pointer can point to any random node of the binary tree or can be null.
Tag: Recursive
Check if a binary tree is a min-heap or not
Given a binary tree, check if it is a min-heap or not. In order words, the binary tree must be a complete binary tree where each node has a higher value than its parent’s value.
Recursively check if the linked list of characters is palindrome or not
Given a linked list of characters, recursively check if it is palindrome or not.
Construct a binary tree from inorder and preorder traversal
Write an efficient algorithm to construct a binary tree from the given inorder and preorder sequence.
Find a triplet with the given sum in a BST
Given a binary search tree, find a triplet with a given sum present in it.
Find minimum jumps required to reach the destination
Given an array of non-negative integers, where each array element represents the maximum number of positions one can move forward from that element. Find the minimum number of jumps required to reach a given destination from a given source within the array.
Merge two BSTs into a doubly-linked list in sorted order
Given two binary search trees, merge them into a doubly-linked list in sorted order.
Find the longest path in a Directed Acyclic Graph (DAG)
Given a directed acyclic graph (DAG) and a source vertex, find the cost of the longest path from the source vertex to all other vertices present in the graph. If the vertex can’t be reached from the given source vertex, print its distance as infinity.
Construct a height-balanced BST from an unbalanced BST
Given a binary search tree (BST), convert it into a height-balanced binary search tree. For a height-balanced binary search tree, the difference between the height of the left and right subtree of every node is never more than 1.
Find the size of the largest BST in a binary tree
Given a binary tree, find the size of the largest BST (Binary Search Tree) in it.
Add a single-digit number to a linked list representing a number
Given a singly linked list whose nodes represent digits of a number, add a single-digit number to it.
Find all Possible Topological Orderings of a DAG
Given a Directed Acyclic Graph (DAG), print all its topological orderings. A Topological ordering of a directed graph G is a linear ordering of the nodes as v1, v2,…,vn such that all edges point forward: for every edge (vi, vj), we have i < j.