How to return the root of a trie that is added to recursively?

Question

I am trying to use a linked list to add a string to a trie with '$' as the terminating character. However, it only returns the last node of the Trie and not the root of the trie. This is my code:

public class DictionaryDLB{

    private Node root;

    private class Node{
        public char value;
        public Node next;
        public Node child;

        public Node() {}
        public Node(char value){
            this.value = value;
            this.next = null;
            this.child = null;
        }
    }
    public void add(String word){
        root = add(root, word, 0);
    }

    private Node add(Node root, String key, int d){
        char c;
        if (d != key.length()) c = key.charAt(d);
        else c = '$';
        if (root == null) root = new Node(c);
        if (d == key.length()) { return root; }
        if (c != root.value) root = add(root.next, key, d);
        return root = add(root.child, key, d+1);
    }

upon completion it returns the node with the value of $ and has no child or next nodes.

Answer 1

The reason is because you're setting root to the return value of add before you return root. The result is that you will get the last instance of root from the call stack. For example, let's say I called add("hi"). Here's how the function call stack would look like assuming root starts off as null,

add("hi")
root = add(root, "hi", 0)
    root = new Node('h')
    return root = add(root.child, "hi", 1)
        root = new Node('i')
        return root = add(root.child, "hi", 2)
            root = new Node('$')
            return root //Node('$')
        return root //Node('$')
    return root //Node('$')
root = root //Node('$')

Notice what's being passed down the function calls is the node with a value of '$'. The reason is that you're setting root to the return value of add at the bottom of your method. There's no need to do this. Just call add like you are doing currently and return root separately like so,

private Node add(Node root, String key, int d){
    char c;
    if (d != key.length()) c = key.charAt(d);
    else c = '$';
    if (root == null) root = new Node(c);
    if (d == key.length()) { return root; }
    if (c != root.value) root.next = add(root.next, key, d);
    else root.child = add(root.child, key, d+1);
    return root;
}

You now have to set the result of add to either root.next or root.child. The reason for this is that the node created in the call to add has to be passed back to set either the next or child pointers. To better illustrate, let's rerun an example stack trace for add("hi").

add("hi")
root = add(root, "hi", 0)
    root = new Node('h')
    root.child = add(root.child, "hi", 1)
        root = new Node('i')
        root.child = add(root.child, "hi", 2)
            root = new Node('$')
            return root //Node('$')
        root.child = root //Node('$')
        return root //Node('i')
    root.child = root //Node('i')
    return root //Node('h')
root = root //Node('h')