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