Gaurav Mishra
BAN USERWon't work at all
First of all the code u provided doesn't even make bst let alone BTREE
Mistake with the code for BST->
Taking ur input 1,4,2,5,3
starts with root as 1
sets left of root as a subtree which has child from the same array with index from(0,1)
Recursively again it goes on to create child of this subtree as another subtree whose left will be from index(0,-1) where u return so right will be 4
it is something like
So left of 1 has 4 which is incorrect,because it will be something like right of left of 1 is 4 which is wrong
import java.lang.*;
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]){
Scanner inp = new Scanner(System.in);
char dict[] = {'a','c','t'};
String words[] = {"cat","act","ac","stop","cac"};
for(String str:words){
Hashtable<Character,Integer> counter = new Hashtable<Character,Integer>();
for(char c:dict){
if(counter.contains(c)){
counter.put(c, counter.get(c) +1);
}
else{
counter.put(c, 1);
}
}
boolean cannotbe=false;
for(char c:str.toCharArray()){
if(counter.get(c)==null){
cannotbe = true;
break;
}
else{
if(counter.get(c)==0){
cannotbe = true;
break;
}
else{
counter.put(c, counter.get(c)-1);
}
}
}
if(!cannotbe){
System.out.println(str);
}
}
}
}
Nope not possible in logn....actually i think it cannot be done in linear time also...it require o(logn) to lookup in a btree.. also just traversing the leaves of btree gives the array in sorted order. Minimum complexity for a comparision based sort is o(nlogn)
- Gaurav Mishra December 19, 2013