Close

## Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination. For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities…

## Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?For example for N = 2, there are 2 such expressions ()()(())For N = 3, there are 5 expressions((()))(()())(())()()(())()()()We have a simple solution to this problem by using recursion. We design this method as follows. It takes two parameters…

## Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not? We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node. Consider the following examples   1          1               1             1  /                       /              …

## Longest path in a binary tree

Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.For example consider the below binary tree The longest path in this tree is 1 – 2 – 3 – 5 – 8 – 6 – 7.…

## Printing all K combinations from N numbers

Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}. For example consider N = 4, K = 3, the possible combinations are [  [1, 2, 3]  [1, 2, 4]  [2, 3, 4]  [1, 3, 4] ] Let us look how to solve this combination problem.…

## Finding the magic index of the array

Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array. So the output is 2.If there no such element in the array…

## Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure. There are three main traversals of the binary tree. Namely In-order traversal Post-order traversal Pre-order traversal In addition to these, there are inverses of the above algorithms, and there is a level order traversal. In this post…

## Finding the height of the binary tree

Given a binary tree how to find the height of the tree.  It is defined as the number of nodes in the longest path from root to any leaf.  We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the…

## Print a string in reverse using recursion

The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the…

## Program to generate all permutations of a given string

This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.We discuss a recursive algorithm as it is simple to understand and implement. Let us…