# Tagged: Recursion

## BST to Greater Sum Tree">Convert BST to Greater Sum Tree

Objec­tive: Given a binary search tree (BST), con­vert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node con­tains the sum of all the nodes…

## Reverse a Linked List in groups of given size ‘K’

Objec­tive: Given a linked list and inte­ger ‘k’, write an algo­rithm to reverse the linked list in groups of size ‘k’. Exam­ple: Approach: Ear­lier we have seen how to reverse a linked list, solu­tion for…

## Get the Sum of all left leaves in a Binary tree

Objec­tive: Given a binary tree, find the sum of all the nodes which are left as well as leaves nodes. Exam­ple:     Approach: Approach is quite sim­ple. Do the inorder tra­ver­sal check if…

## Delete the Binary Tree

Objec­tive: Given a binary tree, write an algo­rithm to delete it. This is one of the basic prob­lem in trees. if you are new to trees then this prob­lem will help you build your…

## Search the Element in a binary tree — With and Without Recursion

Objec­tive: Given a binary tree and a given num­ber x, Write an recur­sive algo­rithm to search the ele­ment in the tree. This is one of the very basic prob­lems of tree. If you are new…

## Tree Traversals

There are mul­ti­ple ways to in which you can tra­verse a tree. In this arti­cle we will see these tra­ver­sals in detail. If you are new to trees then I would rec­om­mend that you…

## Dynamic Programming — Longest Palindromic Subsequence

Objec­tive: Given a string, find a longest palin­dromic sub­se­quence in it. What is Longest Palin­dromic Sub­se­quence: A longest palin­dromic sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not substring)…

## Dynamic Programming — Maximum Product Cutting Problem.

Objec­tive: Given a rope of length n meters, write an algo­rithm to cut the rope in such a way that prod­uct of dif­fer­ent lengths of rope is max­i­mum. At least one cut has to…

## Dynamic Programming — Minimum Numbers are Required Whose Square Sum is Equal To a Given Number

Objec­tive: Given a num­ber, Write an algo­rithm to find out min­i­mum num­bers required whose square is equal to the num­ber. This ques­tion has been asked in the Google Inter­view for Soft­ware Devel­oper posi­tion.This is…

## Dynamic Programming — Longest Common Subsequence

Objec­tive: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them. These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft,…

## Dynamic Programming — Rod Cutting Problem

Objec­tive: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue rn obtain­able by cut­ting up the rod and sell­ing the pieces.…

## Dynamic Programming — Coin Change Problem

Objec­tive: Given a set of coins and amount, Write an algo­rithm to find out how many ways we can make the change of the amount using the coins given. This is another prob­lem in which…

## Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can…

## All N Length Strings from Given String of Length K

Objec­tive: Print All N Length Strings from Given String of Length K where char­ac­ters can appear mul­ti­ple time. Exam­ple: String k = “ALGO” N=2 Result: AA LA GA OA AL LL GL OL AG LG

## Generate Well Ordered Passwords of a Given Length K

Objec­tive: Gen­er­ate Well Ordered Pass­words of a Given Length K. Well ordered means that dig­its should be in increas­ing order in every gen­er­ated pass­word. Exam­ple: K = 7 1234567 1234568 1234569 1234578 1234579 1234589…

## Print All N Length Strings from Given Number K

Objec­tive: Given Num­ber K, Print all the strings of N length. Exam­ple: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3]…

## Print All Possible Subsets with Sum equal to a given Number

Objec­tive: Given a num­ber N, Write an algo­rithm to print all pos­si­ble sub­sets with Sum equal to N In this prob­lem you will see the power of recur­sion. This ques­tion has been asked in the…

## Dynamic Programming — Subset Sum Problem

Objec­tive: Given a set of pos­i­tive inte­gers, and a value sum S, find out if there exist a sub­set in array whose sum is equal to given sum S. Exam­ple: int[] A = {…

## Backtracking — Knight’s Tour Problem

Objec­tive : A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is…

## Backtracking — Search a Word In a Matrix

Objec­tive : Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and…

## Backtracking — N Queens Problem — Better Solution

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Backtracking — N Queens Problem

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Backtracking — Rat In A Maze Puzzle

Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are…

## SUDOKU Solver">Backtracking — SUDOKU Solver

SUDOKU Puz­zle : The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”,…

## Introduction To Backtracking Programming

What is Back­track­ing Pro­gram­ming?? Recur­sion is the key in back­track­ing pro­gram­ming. As the name sug­gests we back­track to find the solu­tion. We start with one pos­si­ble move out of many avail­able moves and try…

## Dynamic Programming — Stairs Climbing Puzzle

Objec­tive: A child is climb­ing up a stair­case with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Imple­ment a method to count how many pos­si­ble ways…

## Dynamic Programming — Minimum Coin Change Problem

Objec­tive: Given a amount ‘A’ and n coins,   v1<v2<v3<.….……<vn . Write a pro­gram to find out min­i­mum num­bers of coins required to make the change for the amount ‘A’. Exam­ple: Amount: 5 Coins []…

## Introduction To Dynamic Programming — Fibonacci Series

What is Dynamic Pro­gram­ming: Dynamic pro­gram­ming is a tech­nique to solve the recur­sive prob­lems in more effi­cient man­ner. Many times in recur­sion we solve the sub-problems repeat­edly. In dynamic pro­gram­ming we store the solution…

## Provide the Next Siblings Pointers in a Given Binary Tree

Objec­tive: — Given a binary tree with three point­ers left, right and nextSi­b­ling). Write the pro­gram to pro­vide the nextsi­b­ling point­ers. Exam­ple: Approach:

## Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Objec­tive: — Given a binary tree and X, Print all the paths start­ing from root so that sum of all the nodes in path equals to a given num­ber. Example:

## Find the Deepest Node in a Binary Tree.

Objec­tive: — Given a binary tree, Find the deep­est node in it. Approach: Take two global vari­able as “deep­estlevel” and “value”. start­ing with level=0, Do the inorder tra­ver­sal and when­ever you go down one level…

## Print All The Full Nodes in a Binary Tree

Objec­tive: Given a binary tree, print all nodes will are full nodes. Full Nodes: Nodes Which has both the chil­dren, left and right are called Full Nodes Approach: quite sim­ple Solu­tion. Do the any of the…

## Print All Combinations of subset of size K from Given Array

Objec­tive: Given an array of inte­gers of size N, print all the sub­sets of size k. (k<=N) Exam­ple: Gen­er­ate all sub­sets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5…

## Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: — Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”. Exam­ple: Given n=2 Out­put: (()) ()() Approach:

## Towers Of Hanoi

The Tower of Hanoi is a math­e­mat­i­cal game or puz­zle. It con­sists of three rods, and a num­ber of disks of dif­fer­ent sizes which can slide onto any rod. The objec­tive of the puz­zle is…

## Generate All Strings of n bits.

Objec­tive: — Gen­er­ate All Strings of n bits, con­sider A[0..n-1] is an array of size n. Exam­ple : n = 3 Out­put: [0, 0, 0]    [1, 0, 0]    [0, 1, 0]    [1, 1, 0] [0,…

## GCD)">Euclidean algorithm — Greatest Common Divisor(GCD)

The great­est com­mon divi­sor (GCD) of two or more inte­gers, when at least one of them is not zero, is the largest pos­i­tive inte­ger that divides the num­bers with­out a remain­der. For exam­ple, the…

## Print the Bottom View of the Binary Tree.

Objec­tive: — Given a binary tree, print it in Bot­tom View of it. What is Bot­tom View: Bot­tom view means when you look the tree from the bot­tom the nodes you will see will be…

## Merge Sort in a Linked list

Objec­tive: Given a Linked List, Sort it using merge sort. Exam­ple: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Ref­er­ence : Merge Sort in array

## Construct a binary tree from given Inorder and Level Order Traversal

Objec­tive: — Given a inorder and level order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and level order tra­ver­sal Appraoch: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder…

## Construct Binary Search Tree from a given Preorder Traversal using Recursion

Objec­tive: — Given a pre­order tra­ver­sal, con­struct BST from that. Input: Pre­order tra­ver­sal Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the — Con­struct Binary Search Tree from a given Pre­order Tra­ver­sal Using Stack (Without…

## Print The Top View of a Binary Tree

Objec­tive: — Given a binary tree, print it in Top View of it. What is Top View: Top view means when you look the tree from the top the nodes you will see will be…

## Construct a Binary Tree from Given Inorder and Depth-First-Search.

Objec­tive: — Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that. Input: Inorder tra­ver­sal and Depth-First-Search. Approach: int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 }; int[] DFS

## Depth First Search/Traversal in Binary Tree

Objec­tive: — Given a Binary Search Tree, Do the Depth First Search/Traversal . Appraoch: Approach is quite sim­ple, use Stack. First add the add to Stack. Pop out an ele­ment from Stack and add its right…

## Inorder Predecessor and Successor in Binary Search Tree

Objec­tive: — Given a Binary Search Tree, Find pre­de­ces­sor and Suc­ces­sor of a given node. What is Pre­de­ces­sor and Suc­ces­sor : When you do the inorder tra­ver­sal of a binary tree, the neigh­bors of given…

## Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or…

## Find Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array Exam­ple: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Out­put: The 4th small­est ele­ment is : 8 Approach: Naive…

## Search an Element in a Rotated Sorted Array

Input: Rotated Sorted Array. What is Rotated Sorted Array. A sorted array is rotated around some pivot ele­ment. See the Exam­ple Below, array is rotated after 6. Approach:

## Print All The Nodes Which are X distance from the Leaf Nodes

Objec­tive: — Given Binary Tree, Print All The Nodes Which are X dis­tance from the Leaf Nodes Exam­ple : Approach:

## Print All The Nodes Which are X distance from the Root

Objec­tive: — Given Binary Tree, Print all the nodes which are X dis­tance from the root Exam­ple : Appraoch: