int[] inOrder = { 4, 2, 6, 5, 7, 1, 3 };
int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };
package javabypatel.tree;
class Node{
private int data;
private Node left;
private Node right;
private Node nextRight; <---- New pointer introduced to connect to adjacent Node.
}
 |
| Check if two trees are mirror images of each other |
 |
| Check if two binary trees are identical or not |
 |
| Insert node in binary search tree in Java |
 |
| Max sum contiguous subarray solution |
 |
| Delete a node in binary search tree cases |
 |
| Binary Tree Example |
 |
| Sample Binary Search Tree |
 |
| Add a node in binary tree |
 |
| Stack trace of printing all possible strings of length K that can be formed from a set of N characters |
package javabypatel;
public class GenerateAllPermutationOfNBits {
public static void main(String[] args) {
permutation("ABC", "", 2);
permutationOfBinaryNumbers("", 2);
}
private static void permutation(String str, String prefix, int lengthOfPermutationString){
if(prefix.length()==lengthOfPermutationString){
System.out.println(prefix);
}else{
for (int i = 0; i < str.length(); i++) {
permutation(str, prefix + str.charAt(i), lengthOfPermutationString);
}
}
}
private static void permutationOfBinaryNumbers(String prefix, int lengthOfPermutationString){
if(prefix.length()==lengthOfPermutationString){
System.out.println(prefix);
}else{
permutationOfBinaryNumbers(prefix + "1", lengthOfPermutationString);
permutationOfBinaryNumbers(prefix + "0", lengthOfPermutationString);
}
}
}
package javabypatel;
import java.util.Arrays;
public class GenerateAllPermutationOfNBits {
public void printCombination(int[] arr, int i, int lengthOfCombination, int combinationSet) {
if (i == lengthOfCombination) {
System.out.println(Arrays.toString(arr));
return;
}
for (int j=0; j<combinationSet; j++) {
arr[i] = j;
printCombination(arr, i+1, lengthOfCombination, combinationSet);
}
}
public void printCombinationOfGivenSet(char[] arr, int i, int lengthOfCombination, char[] combinationSet) {
if (i == lengthOfCombination) {
System.out.println(Arrays.toString(arr));
return;
}
for (int j=0; j<combinationSet.length; j++) {
arr[i] = combinationSet[j];
printCombinationOfGivenSet(arr, i+1, lengthOfCombination, combinationSet);
}
}
public static void main(String[] args) {
GenerateAllPermutationOfNBits obj = new GenerateAllPermutationOfNBits();
int lengthOfCombination = 2; //(length of the combination to generate)
int combinationSet = 2;
//(2 means use 0 and 1 while generating combination)
//(3 means use 0, 1 and 2 while generating combination)
obj.printCombination(new int[lengthOfCombination], 0, lengthOfCombination, combinationSet);
System.out.println("Print from Given set...");
char[] combinationSetArr = new char[]{'A', 'B', 'C'};
obj.printCombinationOfGivenSet(new char[lengthOfCombination], 0, lengthOfCombination, combinationSetArr);
}
}
From above permutations displayed, we can see relation as n!.So for "AB", total permutations are 2! = 2.
 |
| Stack trace of printing all permutations of a string without duplicates in java |
package javabypatel;
public class StringPermutationWithoutRepetition {
public static void main(String[] args) {
permutation("ABC");
}
private static void permutation(String string) {
printPermutation(string,"");
}
private static void printPermutation(String string, String permutation) {
if(string.length()==0){
System.out.println(permutation);
return;
}
for (int i = 0; i < string.length(); i++) {
char toAppendToPermutation = string.charAt(i);
String remaining = string.substring(0, i) + string.substring(i + 1);
printPermutation( remaining, permutation + toAppendToPermutation);
}
}
}
package javabypatel;
import java.util.ArrayList;
import java.util.List;
class Solution {
public static void main(String[] args) {
System.out.println(new Solution().permuteUnique(new int[] {1,2,1}));
}
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null) {
return null;
}
List<List<Integer>> res = new ArrayList<>();
permuteHelper(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void permuteHelper(int[] nums, boolean[] visited, List<Integer> temp, List<List<Integer>> res) {
if (temp.size() == nums.length) {
if (!res.contains(temp)) {
res.add(new ArrayList<>(temp));
return;
}
}
for (int i=0; i<nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
temp.add(nums[i]);
permuteHelper(nums, visited, temp, res);
temp.remove(temp.size()-1);
visited[i] = false;
}
}
}
}
Another nice way of printing permutations if there are duplicates.package javabypatel;
import java.util.ArrayList;
import java.util.List;
public class StringPermutationWithoutRepetition {
public static void main(String[] args) {
List<Object> list = new ArrayList<Object>();
list.add("a");
list.add("b");
list.add("c");
int[] countList = new int[] {1, 1, 1};
Object[] result = new Object[list.size()];
printPermutations(list, countList, result, 0);
}
private static void printPermutations(List<Object> list, int[] countList, Object[] result, int pointer) {
if (pointer == list.size()) {
printArray(result);
return;
}
for (int i = 0; i < list.size(); i++) {
if (countList[i] == 0) {
continue;
}
result[pointer] = list.get(i);
countList[i] = countList[i] - 1;
printPermutations(list, countList, result, pointer + 1);
countList[i] = countList[i] + 1;
}
}
private static void printArray(Object input[]) {
for (Object ch : input) {
System.out.print(ch);
}
System.out.println();
}
}
Explanation: https://www.youtube.com/watch?v=nYFd7VHKyWQpackage javabypatel;
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> permute(int[] nums) {
if (nums == null) {
return null;
}
List<List<Integer>> res = new ArrayList<>();
permuteHelper(nums, new ArrayList<>(), res);
return res;
}
private void permuteHelper(int[] nums, List<Integer> temp, List<List<Integer>> res) {
if (temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i=0; i<nums.length; i++) {
if (!temp.contains(nums[i])) {
temp.add(nums[i]);
permuteHelper(nums, temp, res);
temp.remove(temp.size()-1);
}
}
}
}
