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 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 a given two Binary Trees are Mirror Image of each other.


How to determine a given two Binary Trees are Mirror Image of each other?



Two Binary Trees are considered mirror image of each other if there left and right child of every node is inter-exchange. (Left child moved to Right and Right chile moved to Left)

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



Determine if Two Binary Trees are identical.


How to determine if two Binary Trees are Identical?



Two Binary Trees are considered equal if they are structurally identical and the nodes have the same value.
 

See below image for better understanding of which Trees are called Identical and which 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?



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.


Largest 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.

Delete a node in Binary Search Tree.

How to delete a Node in Binary Search Tree?


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.

Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

What is Binary Tree Traversal?


From Wiki: 
In computer science, Graph traversal is the problem of visiting all the nodes of a graph in a particular manner, updating and/or checking their values along the way.  Tree traversal is a special case of graph traversal. 

Binary Search Tree sample:


There are 2 types of Graph traversal algorithms, 
1. Breadth First Traversal 
2. Depth First Traversal

Tree is a special kind of Graph, where above 2 traversal means,

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.

So start scanning a Binary Tree level by level and wherever we encounter vacant position, place a new Node there.

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.


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

Find all n length Permutation of a given String.
OR
Print all possible strings 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

Case 1  
  Input: string=AB and length=2
  Output:
    AA
    AB
    BA
    BB
   
Case 2
   Input: string=ABC and length=2
   Output:
    AA
    AB
    AC
    BA
    BB
    BC
    CA
    CB
    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
  
    done.
  

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

package backtracking;

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


You may also like to see


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)

   Case 1
      Input:   A
      output: A
     
  Case 2
      Input: AB
      output:
                AB
                BA
               
  Case 3
      Input:  ABC
      output:
                ABC
                ACB
                BAC
                BCA
                CAB
                CBA
 

Algorithm:


  
How many permutations is possible?

  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.

Program to print all permutations of a string in Java

package backtracking;

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! )

You may also like to see


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.