Implementing the TRIE ADT in java

We already saw the Node structure of the TRIE ADT had a content (char), a marker (boolean) and collection of child nodes (Collection of Node). It now has one more method called as subNode(char). This method takes a character as argument would return the child node of that character type should that be present.

Node.java

package com.vaani.ds.trie;

import java.util.Collection;
import java.util.LinkedList;

/**
 * @author kc
 */
public class Node {
    char content;
    boolean marker; 
    Collection<Node> child;

    public Node(char c){
        child = new LinkedList<Node>();
        marker = false;
        content = c;
    }

    public Node subNode(char c){
        if(child!=null){
            for(Node eachChild:child){
                if(eachChild.content == c){
                    return eachChild;
                }
            }
        }
        return null;
    }
}

Now that we've defined our Node, lets go ahead and look at the code for the TRIE class. Fortunately, the TRIE datastructure is insanely simple to implement since it has two major methods insert() and search(). Lets look at the elementary implementation of both these methods.
Trie.java

package com.vaani.ds.trie;

public class Trie{
    private Node root;

    public Trie(){
        root = new Node(' '); 
    }

    public void insert(String s){
        Node current = root; 
        if(s.length()==0) //For an empty character
            current.marker=true;
        for(int i=0;i<s.length();i++){
            Node child = current.subNode(s.charAt(i));
            if(child!=null){ 
                current = child;
            }
            else{
                current.child.add(new Node(s.charAt(i)));
                current = current.subNode(s.charAt(i));
            }
            // Set marker to indicate end of the word
            if(i==s.length()-1)
                current.marker = true;
        } 
    }

    public boolean search(String s){
        Node current = root;
        while(current != null){
            for(int i=0;i<s.length();i++){    
                if(current.subNode(s.charAt(i)) == null)
                    return false;
                else
                    current = current.subNode(s.charAt(i));
            }
            /* 
             * This means that a string exists, but make sure its
             * a word by checking its 'marker' flag
             */
            if (current.marker == true)
                return true;
            else
                return false;
        }
        return false; 
    }
}

We shall look into the detailed working of the insert() and search() methods in separate posts, but I will tell you the gist of both those methods here. The insert() methods adds a new words to the already existing TRIE data structure. The search() method would return true or false based on whether the search string we specified exist or not.

Take a quick look at the java code above because we are going to use this in the posts that follow.
Inserting in Trie

References
http://www.technicalypto.com/2010/04/trie-data-structure-part-2-node-and.html