Trie datastructure

Trie is a very useful data structure. It finds many uses in string based applications like dictionary, autocomplete, spell check etc.

This blog post is not a tutorial on trie but I am simply sharing my trie implementation in java here.

You could find many other implementations on the internet but I really struggled understanding the other implementations especially the function of getting complete words matching a prefix. So I decided to write my own. Here is my implementation.

You can also find it here

class Node{
	public char d;public boolean e;
	public LinkedList<Node>c;
	public Node(){}
	public Node(char a){d=a;e=Boolean.FALSE;c=new LinkedList<Node>();}
	public Node sub(char a){
		int i;
		if(c.isEmpty()) return null;
		for(i=0;i<c.size();i++)
			if(c.get(i).d==a) return c.get(i);
		return null;
	}
}
class Trie{
	Node root;
	public Trie(){
		root=new Node(' ');
	}
	public void add(String a){
		Node n,cur=root;int len=a.length(),i,j;
		if(len==0) cur.e=Boolean.TRUE;
		else{
			for(i=0;i<len;i++){
				if(cur.sub(a.charAt(i))==null) break;
				cur=cur.sub(a.charAt(i));
			}
			while(i<len){
				n=new Node(a.charAt(i));
				cur.c.add(n);
				cur=cur.sub(a.charAt(i));
				i++;
			}
			cur.e=Boolean.TRUE;
		}
	}
	public boolean search(String a){
		Node cur=root;int i,j,len=a.length();
		for(i=0;i<len;i++) {
			if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
			cur=cur.sub(a.charAt(i));
		}
		if(i==len) return Boolean.TRUE;
		return Boolean.FALSE;
	}
	public boolean searchw(String a){
		Node cur=root;int i,j,len=a.length();
		for(i=0;i<len;i++) {
			if(cur.sub(a.charAt(i))==null) return Boolean.FALSE;
			cur=cur.sub(a.charAt(i));
		}
		return cur.e;
	}
	public String next(String pre){
		Node cur=root;int i,len=pre.length();
		for(i=0;i<len;i++) {
			if(cur.sub(pre.charAt(i))==null) return "";
			cur=cur.sub(pre.charAt(i));
		}
		String res="";
		if(i==len) {
			for(Node a:cur.c)
				res=res+String.valueOf(a.d);
			return res;
		}
		return "";
	}
	public LinkedList<Node> getnode(String pre){
		Node cur=root;int i,j,len=pre.length();
		for(i=0;i<len;i++) {
			if(cur.sub(pre.charAt(i))==null) return null;
			cur=cur.sub(pre.charAt(i));
		}
		if(i==len) return cur.c;
		return null;
	}
	public Vector<String>all=new Vector<String>();
	String tm;
	public Vector<String> getStrings(String pre){
		rec(pre);
		return all;
		//for(String f:all) System.out.println(f);
		//System.out.println(all.size());
	}
	public void rec(String pr){
		LinkedList<Node>nod=getnode(pr);
		for(Node n:nod){
			tm=pr+String.valueOf(n.d);
			if(n.e) {all.add(tm);}
			else {
				rec(tm);
			}
		}
	}
}