How to print a Trie in Java?

Question

I have a trie implementation and I want to print my trie out so I can see what's in it. Preferable in a depth first traversal so the words actually make sense. Here is my code:

package trie;

public class Trie {
    public TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    /*
    public Trie(char c){
        TrieNode t = new TrieNode(c);
        root = t;
    }*/

    public void insert(String s, int phraseNb){
        int i = 0;
        TrieNode node = root;
        char[] string = s.toCharArray();
        TrieNode child = null;

        while(i < string.length){
            child = node.getChild(string[i]);
            if(child == null){
                child = new TrieNode(string[i]);
                node.addChild(child);
            }
            else{
                node = child;
            }
            i++;
        }

        node.endOfWord();
        node.setNb(phraseNb);
    }

    public int[] search(char[] c){
        TrieNode node = root;
        for(int i = 0; i < c.length-1; i++){
            node = root;
            int s = 0;
            while(i+s < c.length){
                TrieNode child = node.getChild(c[i + s]);
                if(child == null){
                    break;
                }
                if(child.isWord()){
                    return new int[] {i, s+1, node.getNb()};
                }
                node = child;
                s++;
            }
        }
        return new int[] {-1, -1, -1};
    }

    public void print(){

    }
}

package trie;

import java.io.*;
import java.util.*;

public class TrieNode {
    private boolean endOfWord;
    private int phraseNb;
    private char letter;
    private HashSet<TrieNode> children = new HashSet<TrieNode>();

    public TrieNode(){}

    public TrieNode(char letter){
        this.letter = letter;
    }

    public boolean isWord(){
        return endOfWord;
    }

    public void setNb(int nb){
        phraseNb = nb;
    }

    public int getNb(){
        return phraseNb;
    }

    public char getLetter(){
        return letter;
    }

    public TrieNode getChild(char c){
        for(TrieNode child: children){
            if(c == child.getLetter()){
                return child;
            }
        }
        return null;
    }

    public Set<TrieNode> getChildren(){
        return children;
    }

    public boolean addChild(TrieNode t){
        return children.add(t);
    }

    public void endOfWord(){
        endOfWord = true;
    }

    public void notEndOfWord(){
        endOfWord = false;
    }
}

Just an explanation as to how to go about doing it or some pseudo code is all I need. Thanks for your time.

Answer 1

This is the full example of Trie Implementation using HashMap.

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

class TrieNode{

    private char c;
    private Map<Character,TrieNode> children = new HashMap<>();
    private boolean isLeaf = false;

    TrieNode(){

    }

    /**
     * @param c the c to set
     */
    public void setC(char c) {
        this.c = c;
    }

    /**
     * @return the children
     */
    public Map<Character, TrieNode> getChildren() {
        return children;
    }

    /**
     * @return the isLeaf
     */
    public boolean isLeaf() {
        return isLeaf;
    }

    /**
     * @return the c
     */
    public char getC() {
        return c;
    }

    /**
     * @param isLeaf the isLeaf to set
     */
    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }
}

class Trie{

    TrieNode rootNode;

    public Trie(){
        rootNode = new TrieNode();
    }

    public void insertWord(String word){
        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Map<Character,TrieNode> children = current.getChildren();
            if(children.containsKey(c)){
                current = children.get(c);
            }
            else{
                TrieNode trieNode = new TrieNode();
                children.put(c, trieNode);
                current = children.get(c);
            }
        }
        current.setLeaf(true);
    }

    public boolean searchWord(String word){
        TrieNode current = rootNode;
        for (int i = 0; i < word.length(); i++) {
            Map<Character,TrieNode> children = current.getChildren();
            char c = word.charAt(i);
            if(children.containsKey(c)){
                current = children.get(c);
            }
            else{
                return false;
            }
        }

        if(current.isLeaf() && current!=null){
            return true;
        }
        else{
            return false;
        }
    }

    public void print(TrieNode rootNode,int level, StringBuilder sequence) {
        if(rootNode.isLeaf()){
            sequence = sequence.insert(level, rootNode.getC());
            System.out.println(sequence);
        }

        Map<Character, TrieNode> children = rootNode.getChildren();
        Iterator<Character> iterator = children.keySet().iterator();
        while (iterator.hasNext()) {
            char character = iterator.next();
            sequence = sequence.insert(level, character); 
            print(children.get(character), level+1, sequence);
            sequence.deleteCharAt(level);
        }
    }
}

class TrieImplementation{
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insertWord("Done");
        trie.insertWord("Dont");
        trie.insertWord("Donor");
        trie.insertWord("Sanjay");
        trie.insertWord("Ravi");
        trie.insertWord("RaviRaj");
        TrieNode root = trie.rootNode;
        trie.print(root,0,new StringBuilder(""));
        System.out.println(trie.searchWord("Dont"));
        System.out.println(trie.searchWord("Donor"));
        System.out.println(trie.searchWord("Jay"));
        System.out.println(trie.searchWord("Saviraj"));
        System.out.println(trie.searchWord("RaviRaj"));
        System.out.println(trie.searchWord("Aaviraj"));
    }
}

Answer 2

Here an example that I just threw together. Not the pretties printing and can only print the Trie once but it gets the job done. Hope it helps.

    import java.util.*;

    public class Trie
    {
      static TrieNode root = new TrieNode();
      static char endMarker = '?';
      public static void main(String[] args)
      {
        System.out.println(checkPresentsAndAdd("test"));
        System.out.println(checkPresentsAndAdd("taser"));
        System.out.println(checkPresentsAndAdd("tester"));
        System.out.println(checkPresentsAndAdd("tasters"));
        System.out.println(checkPresentsAndAdd("test"));
        System.out.println(checkPresentsAndAdd("tester"));

        printTrie(root);
      }

      public static boolean checkPresentsAndAdd(String word)
      {
        TrieNode node = root;
        for(int i = 0; i < word.length(); i++)
        {
          char c = word.charAt(i);
          if(node.checkIfNeighbor(c))
          {
              node = node.getNeighbor(c);
          }
          else
          {
            node.addNeighbor(c);
            node = node.getNeighbor(c);
          }
        }

        boolean nord = false;
        if(!node.checkIfNeighbor(endMarker))
        {
          nord = true;
          node.addNeighbor(endMarker);
        }

        return nord;
      }

      public static void printTrie(TrieNode node)
      {

        if(node == null || node.visited)
            return;

        LinkedList<TrieNode> q = new LinkedList<TrieNode>();

        System.out.println(node);
        node.visited = true;
        q.add(node);

        while (!q.isEmpty())
        {
            TrieNode x = q.removeFirst();
            for(Map.Entry<Character,TrieNode> i : x.neighbors.entrySet())
            {
                if(i.getValue().visited == false)
                {
                   System.out.println(i);
                   i.getValue().visited = true;
                   q.add(i.getValue());
                }
            }
        }
      }
    }

    class TrieNode
    {
      Map<Character, TrieNode> neighbors = new HashMap<Character, TrieNode>();

      boolean visited = false;
      public TrieNode(){}

      public boolean checkIfNeighbor(char c)
      {
        return neighbors.containsKey(c);
      }

      public TrieNode getNeighbor(char c)
      {
        if(checkIfNeighbor(c))
        {
          return neighbors.get(c);
        }

        return null;
      }

      public void addNeighbor(char c)
      {
        TrieNode node = new TrieNode();
        neighbors.put(c, node);
      }

      public String toString()
      {
        StringBuilder sb = new StringBuilder();
        sb.append("Node:[neighbors: ");
        sb.append(neighbors);
        sb.append("]\n");

        return sb.toString();
      }
    }

Answer 3

This might help.

public void printTrie(TrieNode node,String s) {
    String strSoFar = s;
    strSoFar += String.valueOf(node.c);
    if(node.isLeaf)
    {
        System.out.println(strSoFar);
        return;
    }
    else
    {
        Stack<TrieNode> stack = new Stack<TrieNode>();
        Iterator<TrieNode> itr = node.children.values().iterator();
        while(itr.hasNext())
        {
            stack.add(itr.next());
        }
        while(!stack.empty()){
            TrieNode t = stack.pop();
            printTrie(t,strSoFar);
        }

    }
}

Try to call the function ,

trieObject.printTrie(trieObject.getRoot(), "");

Answer 4

The visitor design pattern is often useful when dealing with composite data structures like Trie. It enables a developer to decouple the traversal of the composite data structure from the information retrieved at each node.

One could use the visitor design pattern to print the Trie.

Answer 5

I remember my university times when I tried to print the tree on console. Trie is the same in terms of printing IMO... This is what I did and this is what I suggest you to do as well: Take some paper and draw your trie there. Now think how would you like to print the trie. I think trie is composed like N-tree (not a binary but a tree that has a lot of children). Besides that its a recursive structure just like a tree. So you really can apply here the depth first approach.

Lets assume you want to print a trie like this (node 'a' is a root):

a

  b

     e

     f

     g
  d

this is like a trie that contains words: ad abe abf abg

So you start with a root, accumulate the offset and traverse recursively:

printTrie(Node node, int offset) {
     print(node, offset)
     // here you can play with the order of the children
     for(Node child : node.getChildren()) {
          printTrie(child, offset + 2)
     } 
}

Start your recursion with:

printTrie(root, 0)

And you'll be done

I've used 2 as a constant to play with the offset change coefficient, change it to 3,4 or whatever and see what happens.

Hope this helps. Good luck!