Buttercola: EA: Print a Trie

Buttercola: EA: Print a Trie
Given a Trie, print all words in the Trie

class TrieNode {

    // Initialize your data structure here.

    TrieNode[] children;

    boolean leaf;

     

    public TrieNode() {

        children = new TrieNode[26];   

    }

}

 

public class Solution {

    private TrieNode root;

 

    public Solution() {

        root = new TrieNode();

    }

 

    // Inserts a word into the trie.

    public void insert(String word) {

        if (word == null || word.length() == 0) {

            return;

        }

         

        TrieNode p = root;

         

        for (int i = 0; i < word.length(); i++) {

            char c = word.charAt(i);

            if (p.children[c - 'a'] != null) {

                p = p.children[c - 'a'];

            } else {

                p.children[c - 'a'] = new TrieNode();

                p = p.children[c - 'a'];

            }

        }

         

        p.leaf = true;

    }

 

    // Returns if the word is in the trie.

    public boolean search(String word) {

        if (word == null || word.length() == 0) {

            return false;

        }

         

        TrieNode p = root;

        for (int i = 0; i < word.length(); i++) {

            char c = word.charAt(i);

             

            if (p.children[c - 'a'] == null) {

                return false;

            }

             

            p = p.children[c - 'a'];

        }

         

        if (p.leaf) {

            return true;

        } else {

            return false;

        }

    }

 

    // Returns if there is any word in the trie

    // that starts with the given prefix.

    public boolean startsWith(String word) {

        if (word == null || word.length() == 0) {

            return false;

        }

         

        TrieNode p = root;

        for (int i = 0; i < word.length(); i++) {

            char c = word.charAt(i);

             

            if (p.children[c - 'a'] == null) {

                return false;

            }

             

            p = p.children[c - 'a'];

        }

         

        return true;

    }

   

    public void printTrie() {

        TrieNode p = root;

         

        StringBuffer sb = new StringBuffer();

        printTrieHelper(p, sb);

    }

     

    private void printTrieHelper(TrieNode p, StringBuffer sb) {

        if (p == null) {

            return;

        }

         

        if (p.leaf) {

            System.out.println(sb.toString());

        }

         

        for (int i = 0; i < 26; i++) {

            if (p.children[i] != null) {

                char c = (char) (i + 'a');

                sb.append(c);

                printTrieHelper(p.children[i], sb);

                sb.deleteCharAt(sb.length() - 1);

            }

        }

    }

     

    public static void main(String[] args) {

        Solution sol = new Solution();

        sol.insert("abcd");

        sol.insert("abc");

        sol.insert("abd");

        sol.insert("ad");

         

        sol.printTrie();

    }

}

Read full article from Buttercola: EA: Print a Trie