Given a number, find the next smallest palindrome

Reference
http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

Problem statement
Given a number, find the next smallest palindrome larger than this number. 
For example, 
if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. 
if the input number is “9 9 9″, the output should be “1 0 0 1″.
if the input number is “1 9 1″, the output should be “2 0 2″.

My approach.


Please find below recursive approach for find the next smallest palindrome"

Algorithm :- 
If number is all 9's say 99 then then its palindrome will be 101. For 999 answer is 1001 and so on

For other cases 
if input is 1356 then we will start with first & digit same as input 1 _ _ 1
Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. 
So function call for 35 will return 44
So answer for 1356 is 1 4 4 1

Now if number is 1996 the we will start with 1 _ _ 1
Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. 
So function call for 99 will return 101
So it returned palindrome of length more than 2; it means we should increase outer digit to make it 2 _ _ 2
And we should fill it up with zeros.
Thus answer for 1996 is 2002

Code is shared at 
http://ideone.com/3sGpMr

Java code
package stringsequennce;

import java.util.ArrayList;
import java.util.List;

public class NextBiggerPalindromeNumber {

/**
Given a number, find the next smallest palindrome
Given a number, find the next smallest palindrome larger than this number. For example, if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. And if the input number is “9 9 9″, the output should be “1 0 0 1″.

The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]’ and size of array be ‘n’

There can be three different types of inputs that need to be handled separately.
1) The input number is palindrome and has all 9s. For example “9 9 9″. Output should be “1 0 0 1″
2) The input number is not palindrome. For example “1 2 3 4″. Output should be “1 3 3 1″
3) The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1″. Output should be “1 3 3 1″.
*/
public static void main(String[] args) {
// for(int i=1;i<10;i++){
// System.out.println("i= "+i+" "+getMaxPalindromeOfLenthN(i));
// }
int num=0;

num=999 ;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

num=1234;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

num=191;
System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));

}
public static int getNextHigherPalnidromeNumber(int input){
// Handle single digit numbers
if(input==9) return 11;     // For 9 next palindrome is 11

if(input<9) return input+1; // for 0 to 8 next palindrome is next number

// So now number is two digits or more
// Separate out digits 
int temp = input;
ArrayList<Integer> digitList = new ArrayList<Integer>();
while(temp>0){
digitList.add(temp%10);
temp = temp /10;
}
// digitList(0) is digit at unit place
// digitList(n) will be digit at highest place.

// Now check if input is equal to max palindrome of that length
// In that case next palindrome is min palindrome of lenght+1
if(input==getMaxPalindromeOfLenthN(digitList.size())) 
return getMinPalindromeOfLenthN(digitList.size()+1);

// It is not max palindrome of that length. next palindrome is of same length as input.
/* if input is 1356 then we will start with first & digit same as input 1 _ _ 1
*  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. So function will return 44
*  So answer is 1 4 4 1
*  
*  Now if number is 1996 the we will start with 1 _ _ 1
*  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. So function will return 101
*  So it returned palindrome of length more than 2; it means we should increase outer digit
*  2 _ _ 2
*  And we should fill it up with zeros so answer for 1996 is 2002
*  
*/

// Strip first and last digit
//  for number 7986  List is -> 6,8,9,7
// So starting with digit at index n-2 till index 1; prepare number
int outerdigit   =digitList.get(digitList.size()-1);
// So 7 _ _ 7   is time being 7007.
int returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1) + outerdigit;

temp = 0;
for(int i=digitList.size()-2;i>=1;i--){
temp = temp*10 + digitList.get(i);
}
int palindromeForInnerNumber= getNextHigherPalnidromeNumber(temp);

// for inner number 99 palindrome will be 101. In this case we should increase higher number and use all zeros
// Inner number is of length digitList.size()-2. So palindrome of biggger length id digitList.size()-2+1
// For input number 79998 inner number is 999. And its palindrome is 1001. 
// Now outer number was decided as 7 and we had prepared temporary palindrome as 7_ _7. So we should make it 8_ _ 8 means 8008
if(palindromeForInnerNumber==getMinPalindromeOfLenthN(digitList.size()-2+1)){  
outerdigit++;
returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1)+ outerdigit;
}else{
//  For input 7865 palindrome is decided as 7_ _7 i.e. 7007. Inner number is 86. Its palindrome is 99.
// Now 99 is to be fit into middle slot. So we will multiply it by 10 and add into number
// 7007 + 99*10 = 7007 + 990= 7997
returnVal= returnVal+ palindromeForInnerNumber*10 ;
}
return returnVal;
}

public static int getMinPalindromeOfLenthN(int n){
/* For length min palindromes are as follows
* 1 1
*   2 11
*   3 101
*   4 1001
*   5 10001
*/
// So 1 is present at  10^(n-1) and unit digit
// so number is 10^(n-1) + 1
if(n==1) 
return 1;

return (int)Math.pow(10, n-1) + 1;
}

public static int getMaxPalindromeOfLenthN(int n){
/* For legth max palindromes are as follows
* 1 9
*   2 99
*   3 999
*   4 9999
*/
int num =0;
for(int i=1;i<=n;i++){
num = num*10+9;
}
return num;
}


}

Lowest Common Ancestor (LCA) in a Binary Tree

Reference :- 
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

My approach :-
Method using single traversal & flags(v1 and v2) given in article can be improved further.
There we call find(lca, n2) & find(lca, n1). 
So you are traversing tree twice for looking up two keys.
What if n1 is somewhere down n2 ? All the traversal to reach till n1 is done again. 
Instead you should traverse tree just once and keep track of values found. If you find one key still continue searching further for other key. So all the traversal till this point is not needed again. 
Once you find both keys stop search.

So you maintain two flags to indicate of values are found. Initially both flags are false.
If root is equal to one value then corresponding flag is set.
Then we search sub-trees to in same way. 
After traversal is complete; if if both flag were false before this node checking and both flag are true after this node checking then this node it LCA


Java implementation 
Code is also shared at
http://ideone.com/McU0wN

package tree;

public class TreeNode {
int numKey;
char charKey;
public TreeNode left, right;


TreeNode(int keyVal){
numKey=keyVal;
}

TreeNode(char keyVal){
charKey=keyVal;
}

TreeNode(char keyVal,TreeNode leftChild, TreeNode rightChild){
charKey=keyVal;
left=leftChild;
right=rightChild;
}

public static TreeNode findLCA(TreeNode root, int val1, int val2){
LCA lcaObj = new LCA();
lcaObj.val1=val1;
lcaObj.val2=val2;
return findLCA_internal(root,lcaObj);

}

private static TreeNode findLCA_internal(TreeNode root,LCA lcaObj ){
if(root==null) return null;

if(lcaObj.val1Found && lcaObj.val2Found){
// both values are found at previous level so do nothing more
return null;
}else{
boolean val1FlagBefore = lcaObj.val1Found;
boolean val2FlagBefore = lcaObj.val2Found;

if(!lcaObj.val1Found && root.numKey==lcaObj.val1){
lcaObj.val1Found=true;
}if(!lcaObj.val2Found && root.numKey==lcaObj.val2){
lcaObj.val2Found=true;
}
TreeNode lcaPresentInLeftTree = findLCA_internal(root.left,lcaObj);
if(lcaPresentInLeftTree !=null){
return lcaPresentInLeftTree;
}else{
TreeNode lcaPresentInRightTree  = findLCA_internal(root.right,lcaObj);
if(lcaPresentInRightTree!=null) {
return lcaPresentInRightTree;
}else{
// LCA is not presnt in left tree nor it is present in right tree. So check if this node itself if LCA
//  before this node was checked ;val1 flag was false and afterwards it is true.
// ALSO
// before this node was checked; val2 flag was false and and afterwards it is true.
// This root is the LCA
if(!val1FlagBefore && lcaObj.val1Found && !val2FlagBefore && lcaObj.val2Found){
return root;
}else{
// So either or both of keys are not present in this tree
return null;
}

}
}

}
}

public static void main(String[] args) {
/*
10
/ \
   20  30
   / \
  40 50
  */
TreeNode root = new TreeNode(10);
root.left= new TreeNode(20);
root.left.left= new TreeNode(40);
root.left.right= new TreeNode(50);
root.right= new TreeNode(30);

TreeNode lcaNode = null;
lcaNode = findLCA(root, 50, 40);
System.out.println("findLCA(root, 50, 40)" + lcaNode.numKey );
lcaNode = findLCA(root, 30, 40);
System.out.println("findLCA(root, 30, 40)"+ lcaNode.numKey );
lcaNode = findLCA(root, 30, 20);
System.out.println("findLCA(root, 30, 20)"+ lcaNode.numKey );
lcaNode = findLCA(root, 50, 20);
System.out.println("findLCA(root, 50, 20)"+ lcaNode.numKey );

}

}


class LCA{
int val1,val2;
boolean val1Found=false;
boolean val2Found=false;

}


Output

findLCA(root, 50, 40)20
findLCA(root, 30, 40)10
findLCA(root, 30, 20)10
findLCA(root, 50, 20)20

Find the height of the tree represented as array

Reference :-
http://www.geeksforgeeks.org/amazon-interview-experience-set-134-campus-sde
"Attempt 2 F2F – Round 3: Q3"

Problem statement :-

An array is given whose every ith index is the child node of a[i] as shown in the example below. The root node is represented by -1. 

Find the height of the tree.I did it in linear time.

Input: parent[] = {1 2 -1 2}

index                     0 1 2  3

for index 2 value is -1. So it is root   2
for index and index 3 value is 2. So they are child of 2  
          2
        /  \
       1    3
     
for index 0 value is 1. So it is child of 1

         2
        /  \
       1    3
      /    
     0

Height of this tree is 3

My approach :- 

Height of the tree  = maximum number in the array + 1 =  2+1 =3

Another example

Input: parent[] = 1 3 -1  2  1
Index                  0 1  2  3  4

Tree is 
     2
    /
   3
  /
 1
/ \
0  4
    \
     5

Height of this tree is 5


My approach :- 
Height of the tree  = maximum number in the array + 1 =  4+1 =5

Construct Full Binary Tree from given preorder and postorder traversals

Reference
http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/

Problem statement :-
A Full Binary Tree is a binary tree where every node has either 0 or 2 children

It is not possible to construct a general Binary Tree from preorder and postorder traversals (See this). But if know that the Binary Tree is Full, we can construct the tree without ambiguity. Let us understand this with the help of following example.

Let us consider the two given arrays as pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} and post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};
In pre[], the leftmost element is root of tree. Since the tree is full and array size is more than 1. The value next to 1 in pre[], must be left child of root. So we know 1 is root and 2 is left child. How to find the all nodes in left subtree? We know 2 is root of all nodes in left subtree. All nodes before 2 in post[] must be in left subtree. Now we know 1 is root, elements {8, 9, 4, 5, 2} are in left subtree, and the elements {6, 7, 3} are in right subtree.


                  1
                /   \
               /      \
     {8, 9, 4, 5, 2}     {6, 7, 3}
We recursively follow the above approach and get the following tree.

          1
        /   \
      2       3
    /  \     /  \
   4    5   6    7
  / \  
 8   9 

My Java implementation

import java.util.Queue;

import java.util.concurrent.LinkedBlockingQueue;

class TreeNode {

  

    // data members

 public int key;

 public char charkey;

    public TreeNode left;

    public TreeNode right;

  

    // Constructor

    public TreeNode(int key) { this.key = key; left = null; right = null; }

    public TreeNode(char charkey) { this.charkey = charkey; left = null; right = null; }

  

    // Methods to set left and right subtrees

    public void setLeft(TreeNode left)   { this.left = left; }

    public void setRight(TreeNode right) { this.right = right; }

    

    public static void printLevelOrder(TreeNode root)

    {

      Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); 

      

      while(root != null){

       System.out.println(root.charkey);

       if(root.left!=null){

        queue.add(root.left);

       }

       if(root.right!=null){

        queue.add(root.right);

       }

       root = queue.poll();

      }

    }

}

 public class ConstructTreeFromTraversal {

  

   int preOrderIndex=0;

   String inorder, preorder ,postorder;

  

 

 public static void main(String[] args) {

/* postorder preorder  test */

ConstructTreeFromTraversal obj = new ConstructTreeFromTraversal();

obj.postorder="894526731";

obj.preorder="124895367";

TreeNode root = obj.constructTree_Preorder_Postorder();

TreeNode.printLevelOrder(root);

System.out.println("Done");

}

 public TreeNode constructTree_Preorder_Postorder(){

return constructTree_Preorder_Postorder_inernal(postorder);

}

public TreeNode constructTree_Preorder_Postorder_inernal(String postorder){

if(postorder.equals("")){

return null;

}

// preOrderIndex which is initialized as zero indicates current position in preorder

// that is to be considered as root

char rootKey = preorder.charAt(preOrderIndex);

preOrderIndex++;

TreeNode root = new TreeNode(rootKey);

if(postorder.length()>1){

// In post-order last element will be root. So we will omit it for further process

// And split the string into two parts based on left child

String tempStringWithoutRoot = postorder.substring(0,postorder.length()-1);

char leftChildKEy = preorder.charAt(preOrderIndex);

if(tempStringWithoutRoot.length()>1){

String [] child = tempStringWithoutRoot.split(leftChildKEy+"");

TreeNode leftChild = constructTree_Preorder_Postorder_inernal(child[0]+leftChildKEy);

root.setLeft(leftChild);

if(child.length>1){

TreeNode rightChild = constructTree_Preorder_Postorder_inernal(child[1]);

root.setRight(rightChild);

}

}else{

TreeNode leftChild = constructTree_Preorder_Postorder_inernal(tempStringWithoutRoot);

}

}

return root;

}

}

Output

1

2

3

4

5

6

7

8

9

Done

Construct tree from inorder and preorder traversal

Reference :-
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Problem Statement :-
Construct binary tree from inorder and preorder traversal
Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C
We recursively follow above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

My java implementation :-

import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

class TreeNode {
  
    // data members
public int key;
public char charkey;
    public TreeNode left;
    public TreeNode right;
  
    // Constructor
    public TreeNode(int key) { this.key = key; left = null; right = null; }
    public TreeNode(char charkey) { this.charkey = charkey; left = null; right = null; }
  
    // Methods to set left and right subtrees
    public void setLeft(TreeNode left)   { this.left = left; }
    public void setRight(TreeNode right) { this.right = right; }
    
    public static void printLevelOrder(TreeNode root)
    {
      Queue<TreeNode> queue = new LinkedBlockingQueue<TreeNode>(); 
      
      while(root != null){
     System.out.println(root.charkey);
     if(root.left!=null){
     queue.add(root.left);
     }
     if(root.right!=null){
     queue.add(root.right);
     }
     root = queue.poll();
      }
    }
}


 class ConstructTreeFromTraversal {
 
int preOrderIndex=0;
String inorder, preorder;

public static void main(String[] args) {

ConstructTreeFromTraversal obj = new ConstructTreeFromTraversal();
obj.inorder="DBEAFC";
obj.preorder="ABDECF";
TreeNode root = obj.constructTree();
System.out.println("Printing Level order traversal");
TreeNode.printLevelOrder(root);
System.out.println("Done");
}

public TreeNode constructTree(){
TreeNode root = constructTree_internal(inorder);
return root;

}
public TreeNode constructTree_internal(String inorder){
if(inorder.equals("")){
return null;
}
// preOrderIndex which is initialized as zero indicates current position in preorder
// that is to be considered as root
char rootKey = preorder.charAt(preOrderIndex);
preOrderIndex++;
TreeNode root = new TreeNode(rootKey);
// See it length of inorder is more than 1 i.e. it has node other than root
if(inorder.length()>1){
// Find rootKey in inOrder and split it into two parts
String [] child = inorder.split(rootKey+"");
try{
TreeNode leftChild = constructTree_internal(child[0]);
root.setLeft(leftChild);
// Call if right nodes are present
if(child.length>1){
TreeNode rightChild = constructTree_internal(child[1]);
root.setRight(rightChild);
}
}catch (Exception e){
e.printStackTrace();
}
}
return root;
}

}

Output

Printing Level order traversal

A

B

C

D

E

F

Done

Print all nodes between levels ‘m’ and ‘n’ in level in binary tree

Reference

http://www.geeksforgeeks.org/amazon-interview-experience-set-134-campus-sde/

Problem statement

Given ‘m’ and ‘n’ (m < n), print all nodes between levels ‘m’ and ‘n’ in level order.

My approach 

We will modify level order traversal a little bit. We will create a list of nodes on every level.

Create a master list (list of lists) indicating each level
Create a list to indicate 0th level and root to it.
Add this list into master list

Now traverse over master list i.e. traverse over every level one by one. 
Create new list for next level and add the children of node of current level into it.

Once all the levels are traversed print the sublists for required levels.

Java implementation

Also shared at

http://ideone.com/KhLv6E

import java.util.ArrayList;

class TreeNode {

  

    // data members

public int key;

    public TreeNode left;

    public TreeNode right;

  

    // Accessor methods

    public int key()        { return key; }

    public TreeNode left()  { return left; }

    public TreeNode right() { return right; }

  

    // Constructor

    public TreeNode(int key) { this.key = key; left = null; right = null; }

  

    // Methods to set left and right subtrees

    public void setLeft(TreeNode left)   { this.left = left; }

    public void setRight(TreeNode right) { this.right = right; }

    

    

    public static void printLevelOrderBetweenGivenLevels(TreeNode root,int fromLevel,int toLevel)

    {

    if(root!=null){

    ArrayList<ArrayList<TreeNode>> outerList  = new ArrayList<ArrayList<TreeNode>>();

    outerList.add(new ArrayList<TreeNode>());

    outerList.get(0).add(root);

    for(int i=0;i<outerList.size();i++){

ArrayList<TreeNode> currentLevelList = outerList.get(i) ;

    if(currentLevelList.size()>0){

    outerList.add(new ArrayList<TreeNode>());   // Create empty list for next level

    for(TreeNode node : currentLevelList){

    ArrayList<TreeNode> nextLevelList = outerList.get(i+1);

    if(node.left !=null) nextLevelList.add( node.left);

    if(node.right !=null) nextLevelList.add( node.right);

   

    }

    }

    }

   

    // Now print the list element for required levels

    for(int i=fromLevel; i<=toLevel && i<outerList.size() ;i++){

    ArrayList<TreeNode> currentLevelList = outerList.get(i);

    for(TreeNode node : currentLevelList){

    System.out.println(node.key);

    }

    }

    System.out.println("done");

    }

    }

    

    

       public static void main(String[] args) {

        /* Create following Binary Tree

              1

            /    \

          2        3

         / \      / \

        4   5    6   7

  

        */

        TreeNode root = new TreeNode(1);

        root.setLeft(new TreeNode(2));

        root.setRight(new TreeNode(3));

        root.left().setLeft(new TreeNode(4));

        root.left().setRight(new TreeNode(5));

        root.right().setLeft(new TreeNode(6));

        root.right().setRight(new TreeNode(7));

        // Levels start with zero

        TreeNode.printLevelOrderBetweenGivenLevels(root,2,4);

        

    }

}

Output

4
5
6
7
done