Construct a Binary Tree from In-order and Level-order traversals.

How to construct a Binary Tree from given In order and Level order traversals.


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
Two traversals are given as input,
        int[] inOrder =    { 4, 2, 6, 5, 7, 1, 3 };
        int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 };

By using above 2 given In order and Level Order traversal, construct Binary Tree like shown below,



Connect nodes at same level in a binary tree using constant extra space.

How to connect nodes at same level using constant extra space? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
 Binary Tree is given to you, 
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null.  
Our task is to connect nextRight pointer of each node to its adjacent node. 
  1. If the immediate adjacent node is not present then connect to next adjacent node and 
  2. If next adjacent node is not present then connect to next to next adjacent node and 
  3. If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
  4. If the adjacent node is not present at same level then connect it to null.
See below image for better understanding the problem statement.


Connect nodes at same level in a Binary Tree.

How to connect nodes at same level using Queue? OR
Populate next right pointers for each Tree Node? OR
Connect nodes of a binary tree at same Level?


Let us first understand what we want to achieve? what is the input and what will be the expected output?

Question:
 Binary Tree is given to you,
  1. some node of  tree has both left and right child present,
  2. some node of tree has only left child present and
  3. some node of tree has only right child present, 
  4. nextRight pointer of all the node initially is null. 
Our task is to connect nextRight pointer of each node to its adjacent node.  
  1. If the immediate adjacent node is not present then connect to next adjacent node and 
  2. If next adjacent node is not present then connect to next to next adjacent node and 
  3. If next to next adjacent node is not present then search until you find the adjacent node along the same Level and connect to it.
  4. If the adjacent node is not present at same level then connect it to null. 


Structure of the given Binary Tree Node is like following:
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.
}


See below image for better understanding the problem statement.


Check if two trees are mirror images of each other

How to check if two binary trees are mirror images of each other?


In this post we will look at algorithm to check if two trees are mirror images of each other with Java program.

See below image for better understanding of which Trees are called Mirror Image of each other

check if two trees are mirror images
Check if two trees are mirror images of each other

Check if two binary trees are identical

Check if two binary trees are identical or not?


In this post we will check if given binary trees are identical or not using recursive approach.
 
See below image for better understanding of which Trees are called Identical and which not.
check if two binary trees are identical or not in Java
Check if two binary trees are identical or not

Binary Search Tree Operations ( Add a node in Binary Search Tree, Search a node in Binary Search Tree ).

How to Add a Node and Search a Node in Binary Search Tree?


Let's see how to insert a node in binary search tree (BST) and search a node in binary search tree.

What is Binary Search Tree?
In computer science, Binary Search Trees (BST), sometimes called Ordered or sorted binary trees, are a particular type of containers: data structures that store "items" (such as numbers, names and etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
More: https://en.wikipedia.org/wiki/Binary_search_tree


While adding a Node in a Binary Search Tree, it should follow below rules,
  1. All values descending on the Left side of a node should be less than (or equal to) the node itself. 
  2. All values descending on the Right side of a node should be greater than (or equal to) the node itself.
If Tree follows above protocol for all the Nodes of a tree, then Tree is called a Binary Search Tree. See below image to get better understanding of Binary Search Tree rules.
add a node in binary search tree in java
Insert node in binary search tree in Java

Maximum Sum Contiguous Subarray using Kadane's algorithm.

Find the maximum-sum subarray of an array. OR
Explain Kadane's Algorithm to solve the Maximum Sum Subarray OR
Find Largest Sum Contiguous Subarray.

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
max sum contiguous subarray in java
Max sum contiguous subarray solution

Delete a node in Binary Search Tree in Java

How to delete a Node in Binary Search Tree in Java?


Let's see how to delete a node in binary search tree with example and java program. 

There are 3 cases that need to be considered while deleting a node from Binary Search Tree.
  1. Node to delete has no children that is no left child and no right child present. Case 1 in below image. 
  2. Node to delete has only one child either left child or right child present. Case 2 in below image.
  3. Node to delete has both child that is left child and right child present. Case 3 in below image.
delete a node in binary search tree
Delete a node in binary search tree cases

Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

What is Binary Tree Traversal?


Binary tree traversal is a way to read a tree by visiting each node in a particular manner. 
We will look into three popular binary tree traversal, Inorder, Preorder and Postorder along with example.

Note: Tree traversal (Inorder, Preorder and Postorder) are classified as a part of Graph traversal because Tree is a special kind of Graph.

There are mainly 2 types of Graph traversal algorithms Breadth first traversal and Depth First traversal and is divided as follows,
  1. Depth First Traversal
    1. Inorder traversal
    2. Preorder traversal
    3. Postorder traversal
  2. Breadth First Traversal
    1.  Level Order Traversal 

Add a node in Binary Tree and not a Binary Search Tree.

How to add a Node in Binary Tree and not a Binary Search Tree?


To add a Node in a Binary Tree, Let us first fix our protocol of how we are going a insert a node in Binary Tree.

Before going further, I would like to clear the difference between Binary Tree and Binary Search Tree, you are welcome to skip this part if you are already aware of,

Binary Tree: A tree is called Binary Tree if each node of tree has no more than 2 child node.
sample binary tree
Binary Tree Example
If you want to look at popular Binary tree traversals, 

Binary Search Tree: It is a special type of Binary Tree where it follow below rules,
  1. Nodes on left subtree must have value less than the parent node.
  2. Nodes on right subtree must have value greater than the parent node.
binary search tree example
Sample Binary Search Tree

How to add a Node in Binary Tree:

For adding a node in Binary tree we just need to make sure we are not breaking the rule of Binary tree that is, "each node of tree has no more than 2 child node".

So to add a node, we will start scanning a Binary Tree level by level and wherever we encounter a Node which has no child node or has only one child node, that would be our target node to insert a new Node

See below image to get better understanding of position of a new Node to insert. Given a binary tree, we need to add a Node with value 8 marked in dotted lines below in its correct position.
add a node in binary tree algorithm
Add a node in binary tree

Print all possible strings of length K that can be formed from a set of N characters in Java

Find all n length Permutation of a given String.
OR
Print all combinations/permutations of a string of length k that can be formed from a set of n characters. OR.
Print all possible combinations of k elements from a given string of size n

Print all possible strings of length K that can be formed from a set of N characters in Java. Lets see sample input and output below,

Case 1  
Input: string=AB and length=2
Output:

  1. AA
  2. AB
  3. BA
  4. BB
Case 2
Input: string=ABC and length=2
Output:

  1. AA
  2. AB
  3. AC
  4. BA
  5. BB
  6. BC
  7. CA
  8. CB
  9. CC  

Algorithm:


How many permutations is possible?

How many permutations is possible can be calculated using k^r where,
  k = length of unique characters to use.
  r = number of places to fill. 


In first example above, 
k=2(A,B), r=2(all permutations of length 2 is required) 
= 2^2 = 4 permutations possible.

In second example above, 

k=3(A,B,C), r=2(all permutations of length 2 is required)
3^2 = 9 permutations possible.
 

How to print all permutation?

It is very easy, Lets take an example of String "ABC" and we are told to generate permutations of length 3.    

using formula k^r we can see, 3^3 = 27 permutations possible.
We will take recursive approach i
n this approach important thing is base case.

Base Case: 

We will try to make each permutation by adding characters one by one to the temporary
string "permutation" that need to be printed.
We will add the characters to the string "permutation" until the length of it is 3 as we want to find permutations of length 3.
  
So base case is, when the length of our string "permutation" matches given length, 

we will print the string "permutation" and return.
 

Working:
  
Now, how we will form "permutation" string is,
we have string "ABC" and we want to find all permutation of it consisting of length 3.
  
How we can do is,

First lets see how many permutation possible of length 1 of given string "ABC".
Answer is 3.
     A
     B
     C

So we can see that if we fill our third position by keeping first 2 place common, filled by "A", 

and only changing last place to possible permutation of length 1, we will get 3 permutations.
    
     A A A
     A A B
     A A C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
    
     A B A
     A B B
     A B C
  
and now if we repeat the same, but this time we will change the second position and then again iterate over possible permutation of length 1, we will again get 3 permutations.
  
     A C A
     A C B
     A C C
  
and now if we repeat the same, but this time we can't change the second position as we have covered second place for all possible characters "A", "B" and "C" keeping "A" at first place fixed.
 

So, Now it is the time to change the first place position which is till now covered only for "A".
So this time we will change the first place position to "B" and again we will repeat above steps.
  
    B A A
    B A B
    B A C
  
    then,
  
    B B A
    B B B
    B B C
  
    then,
  
    B C A
    B C B
    B C C
  
So, now it is the time to change the first place position which is till now covered only for 

"A" and "B".
We will change the first place position to "C" and again we will repeat above steps.

    C A A
    C A B
    C A C
  
    then,
  
    C B A
    C B B
    C B C
  
    then,
  
    C C A
    C C B
    C C C

Print all possible strings of length k that can be formed from a set of n characters
Stack trace of printing all possible strings of length K that can be formed from a set of N characters

Program to print all combinations of string of length k in Java

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);
  }
 }
 
}

Another approach

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);
    }
}

Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Print all subsets of a given set.


Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Write a program to print all permutations of a given string without repetition. (Repetition of characters is not allowed).

Given a string of length n, print all permutation of the given string without Repetition . (Repetition of characters is NOT allowed)

Print all the permutations of a string without repetition in Java. lets understand with sample input and output below, 

Case 1
Input: A
Output: A
     
Case 2
Input: AB
Output:
  1. AB
  2. BA
Case 3
Input:  ABC
Output:
  1. ABC
  2. ACB
  3. BAC
  4. BCA
  5. CAB
  6. CBA 

How many permutations is possible:


Algorithm

 Lets see how many permutation is possible for given n character String.
 In string "AB", n is 2
 In string "ABC", n is 3
  From above permutations displayed, we can see relation as n!.
 So for "AB", total permutations are 2! = 2.
 For "ABC", total permutations are 3! = 6.

How to print all permutation?

It is very easy, Lets take an example of String "ABC"
 
We will take recursive approach. In this approach important thing is base case.
We will try to make each permutation by adding characters one by one to the temporary 
string  "permutation" that need to be printed and removing the same character one by one 
from original string. As we are removing one by one character from original string and adding it to "permutation" string,   So it is sure at one point length of original String will be 0 and length of 
"permutation" string will be 3.
 
So base case is, when the length of our original string became 0, we will print the string  "permutation" and return.
 
Now, how we will form "permutation" string is, 
remove first character of original string and add it to "permutation" string and check the 
length of original string which is not 0, true, so call function again,

"string" = "BC" "permutation" = "A"
     
remove first character of original string and add it to "permutation" string and check the length of original string which is not 0, true, so call function again,

"string" = "C" "permutation" = "AB"
     
remove remaining character of original string and add it to "permutation" string and check the length of original string which is not 0, false, so it is time to print the string "permutation".

"string" = "" "permutation" = "ABC"
     
1st permutation is ABC

after returning from printing 1st permutation,
      "string" = "C" "permutation" = "AB" 
              Original string has only one character "C" whose permutation is covered, 
              no more permutation possible of one character string, so return,

      "string" = "BC" "permutation" = "A"
               From original string "ABC", we covered permutation keeping 
              "A", "B" at place and changing "C", which gave "ABC" as 1st permutation.
               Now, its time to work on 2nd character of original string

Now, remove second character of original string and add it to "permutation" string and check the 
length of original string which is not 0, true, so call function again,
       "string" = "B" "permutation" = "AC"
     
remove remaining character of original string and add it to "permutation" string and check the length of original string which is not 0, false, so it is time to print the string "permutation".
      "string" = "" "permutation" = "ACB"
     
if we continue the same process in a loop, then we will get all our permutations without repetition of characters.
print all permutations of a string without duplicates in java
Stack trace of printing all permutations of a string without duplicates in java

Program to Print 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);
  }  
 }
}

Time Complexity:


Time complexity of program to print all permutations of a string is O(n*n!).

How it comes to (n * n!)
From the above stack trace picture of a program you can see, for printing permutation of string "ABC" i.e. 3 character word, what it does is 

Outer:
Keeping A at place, it finds all the permutations of remaining string, then,
          Inner:
          Keeping B at place, it finds all the permutations of remaining string, then,
                     keeping C at place, it finds all the permutations of remaining string, then,
          Change B to C and find all the permutations of remaining string, then, 
                     ...........
           ...............             
Keeping B at place, it finds all the permutations of remaining string, then,
           ...........
           ...........
Keeping C at place, it finds all the permutations of remaining string.

How many times Outer: label has to print is number of characters present in word.
that is n
How many times Inner: label has to print is number of permutations of a character present in word.
this brings n!
 
Now, if we read this line again,
Keeping Outer character at place, find all permutation of Inner sting, then replace 
Outer character at place, and again find all permutation of Inner sting, and 
so on till end of Outer character.

hence the complexity is O(n * n! )

Another approach that work with duplicates (LeetCode 47. Permutations II)

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=nYFd7VHKyWQ

If there are NO duplicates. (Leetcode 46. Permutations)


package 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);
            }
        }
    }
}
  

Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

Print all subsets of a given set.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.