How to find the longest word in a prefix tree recursiverly?

Question

I have the following data structure: This tree stores only characters in lowercase.

I'm trying to build a method that finds the longest word in the tree recursively. I have difficulty to build this method that checks each branch of the nodes recursively.

Here the given classes I'm using, showing only the relevant methods:

public class Tree {

    private final Node root;

    public Tree() {
        root = new Node('0');
    }

 private String getWordOfBranch(final Node[] nodes, final int i) {

        if (nodes[i] == null) {
            return "";
        }

        if (nodes[i].isLeaf()) {
            return String.valueOf(nodes[i].getValue());
        }

        return nodes[i].getValue() + getWordOfBranch(nodes[i].children, i);
    }

public class Node {

    private final char value;
    protected Node[] children;

    public Node(final char value) {
        this.value = value;
        children = new Node[26];
    }

  public boolean isLeaf() {
        for (final Node child : children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }

    public char getValue() {
        return value;
    }

Answer 1

Well, in this case, you are only taking the word starting at a specific position i. What you should be doing is looping through all of the children and finding the longest word out of all of the children. Also, your node class should not be having a set amount of children, but instead a dynamically sized list of children, using something like an ArrayList to store the children, since each node does not have to have a specific set of children.

    public class Node {

        private final char value;
        protected ArrayList<Node> children;

        public Node(final char value) {
            this.value = value;
            children = new ArrayList<Node>();
        }

        public boolean isLeaf() {
            for (final Node child : children) {
                if (child != null) {
                    return false;
                }
            }
            return true;
        }

        public char getValue() {
            return value;
        }

        public ArrayList<Node> getChildren() {
            return children;
        }

    public String getLargestWord(Node root) {
        if (root.isLeaf()) {
            return String.valueOf(root.getValue());
        }

        else {
            String longest = "";
            for (Node child : root.getChildren()) {
                String longWordInChild = getLongestWord(child);
                if (longWordInChild.length() > longest.length()) {
                    longest = longWordInChild;
                }
            }

            return root.getValue() + longest;
        }
    }

Answer 2

I made some changes to your code.
First the Node class.

import java.util.ArrayList;
import java.util.List;

public class Node {
    private final char  value;
    protected List<Node> children;

    public Node(char letter) {
        value = letter;
        children = new ArrayList<>();
    }

    private static boolean isValidValue(Node node) {
        boolean isValid = false;
        if (node != null) {
            char ch = node.getValue();
            isValid = 'a' <= ch  &&  ch <= 'z';
        }
        return isValid;
    }

    public boolean addChild(Node child) {
        boolean added = false;
        if (child != null) {
            if (isValidValue(child)) {
                boolean found = false;
                for (Node kid : children) {
                    found = kid != null  &&  kid.getValue() == child.getValue();
                    if (found) {
                        break;
                    }
                }
                if (!found) {
                    added = children.add(child);
                }
            }
        }
        return added;
    }

    public List<Node> getChildren() {
        return children;
    }

    public char getValue() {
        return value;
    }
}

I used List for the children, rather than an array, because an array has a fixed size and a List does not.

Now the Tree class. Note that I added a main() method to the class just for testing purposes. The main() method creates the tree structure in the image in your question.

A tree data structure has levels and also has leaves. A leaf is a node in the tree that has no child nodes. Hence every leaf in your tree is the last letter of a word. The leaves at the highest level represent the longest words. (Note that the level of the root node in the tree is zero.)

import java.util.ArrayList;
import java.util.List;

public class Tree {
    private int  longest;
    private List<String>  words;
    private Node  root = new Node('\u0000');

    public List<String> getWords() {
        return words;
    }

    public Node getRoot() {
        return root;
    }

    public void visit() {
        visit(root, 0, new StringBuilder());
    }

    public void visit(Node node, int level, StringBuilder word) {
        if (node != null) {
            word.append(node.getValue());
            List<Node> children = node.getChildren();
            if (children.size() == 0) {
                if (level > longest) {
                    longest = level;
                    words = new ArrayList<>();
                }
                if (level == longest) {
                    words.add(word.toString());
                }
            }
            else {
                for (Node child : children) {
                    word.delete(level, word.length());
                    visit(child, level + 1, word);
                }
            }
        }
    }

    /**
     * For testing only.
     */
    public static void main(String[] args) {
        Tree tree = new Tree();
        Node root = tree.getRoot();
        Node j = new Node('j');
        root.addChild(j);
        Node r = new Node('r');
        root.addChild(r);
        Node a = new Node('a');
        j.addChild(a);
        Node v = new Node('v');
        a.addChild(v);
        Node a2 = new Node('a');
        v.addChild(a2);
        Node a3 = new Node('a');
        r.addChild(a3);
        Node o = new Node('o');
        r.addChild(o);
        Node d = new Node('d');
        a3.addChild(d);
        Node n = new Node('n');
        a3.addChild(n);
        Node d2 = new Node('d');
        n.addChild(d2);
        Node u = new Node('u');
        a3.addChild(u);
        Node m = new Node('m');
        u.addChild(m);
        Node s = new Node('s');
        o.addChild(s);
        Node e = new Node('e');
        s.addChild(e);
        tree.visit();
        System.out.println(tree.getWords());
    }
}

Method visit(Node, int, StringBuilder) is the recursive method. It traverses every path in the tree and appends the characters in each node to a StringBuilder. Hence the StringBuilder contains the word obtained by traversing a single path in the tree - from the root to the leaf.

I also keep track of the node level since the highest level means the longest word.

Finally I store all the longest words in another List.

Running the above code produces the following output:

[java, rand, raum, rose]