Tree

A tree stores nodes. Each node can reference other nodes—these are child nodes. In Java we can develop a simple tree to store many strings.

With this method, we store a HashMap on each node. This map points to child nodes. To traverse the tree, we access elements in the HashMap.

Example program

This program is simple. We first see the TreeNode class—this contains the children node (in a HashMap). We also have get and add() methods.

Start In the Program class we have an addWord and an exists() method. These handle strings and manipulate the tree.

Next AddWord() loops over all the characters in the String. It calls add() on each letter to add nodes.

Finally Exists() tests the tree to see if a string exists in it. The result is a boolean.

import java.util.HashMap;

class TreeNode {
    boolean word;
    HashMap<Character, TreeNode> children = new HashMap<>();

    public TreeNode get(char value) {
        // Get anode from the HashMap.
        return children.getOrDefault(value, null);
    }

    public TreeNode add(char value, TreeNode node) {
        // Add a node if one does not yet exists.
        // ... Return the matching node.
        children.putIfAbsent(value, node);
        return get(value);
    }
}

public class Program {

    static TreeNode root = new TreeNode();

    static void addWord(String value) {
        // Add all characters from the string to the tree.
        TreeNode node = root;
        for (int i = 0; i < value.length(); i++) {
            node = node.add(value.charAt(i), node);
        }
        node.word = true;
    }

    static boolean exists(String value) {
        // See if a word exists in the tree.
        TreeNode node = root;
        for (int i = 0; i < value.length(); i++) {
            node = node.get(value.charAt(i));
            if (node == null) {
                return false;
            }
        }
        return node.word;
    }

    public static void main(String[] args) {

        // Add three words to the tree.
        addWord("cat");
        addWord("bird");
        addWord("dog");

        // These three words should exist.
        boolean exists1 = exists("cat");
        boolean exists2 = exists("bird");
        boolean exists3 = exists("dog");
        System.out.println(exists1);
        System.out.println(exists2);
        System.out.println(exists3);

        // These words do not exist.
        exists1 = exists("fish");
        exists2 = exists("123456");
        exists3 = exists("turnip");
        System.out.println(exists1);
        System.out.println(exists2);
        System.out.println(exists3);
    }
}true
true
true
false
false
false

Tests

In the main() method we test the tree with the addWord and exists() methods. We add three strings—exists returns true on these strings.

And The exists() method fortunately returns false on the strings we did not add to the tree.

Some performance issues

A tree like this one can be used to optimize string lookups. This can implement a Scrabble or anagram program.

However The implementation here is not perfect. The HashMap could be changed to an array of TreeNode references.

And With an array, we could lazily allocate the array to save memory. We could use a lookup method to match chars to indexes.

A review

Trees (tries) are powerful. In the field of artificial intelligence, nodes represent search steps. And traversing a tree is a performance challenge.