Skip to main content

Trie

class Trie {
    private static class Node {
        public Node[] children;
        public boolean isEnd;
        public Node() {
            this.children = new Node[26];
            this.isEnd = false;
        }
    }
    private Node root;
    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        root = insert(root, word, 0);
    }

    private Node insert(Node node, String word, int depth) { // p
        if (depth == word.length()) {
            node.isEnd = true;
            return node;
        }
        char childChar = word.charAt(depth); // p
        int charIndex = childChar - 'a'; // 15
        if (node.children[charIndex] == null) {
            node.children[charIndex] = new Node();
        }
        node.children[charIndex] = insert(node.children[charIndex], word, depth + 1);

        return node;
    }
    
    public boolean search(String word) {
        return search(root, word, 0);
    }

    private boolean search(Node node, String word, int depth) {
        if (node == null) {
            return false;
        }
        if (depth == word.length()) {
            return node.isEnd;
        }
        char childChar = word.charAt(depth);
        int charIndex = childChar - 'a';
        return search(node.children[charIndex], word, depth + 1);
    }
}

Trie drawing on the computer​

insert(ap, 3), insert(b, 2)
root depth=0, val=5
[a]                    [b]
|                      |
a depth=1, val=3.      b depth=1, val=2
[p]                    isEnd = true
|
p depth=2, val=3
isEnd = true