How to implement remove method in Trie data structure?

Question

I am trying to implement PatriciaTrie data structure. I was recently asked this question in a coding interview through Google Docs. But I was not able to answer this.

I made some progress by adding insert method in the below code but got stuck on the remove method in the PatriciaTrie code - not sure how to implement that -

Below is my PatriciaTrie code -

public class PatriciaTrie {

    protected static class Edge {
        Node target;
        TTString label;
        public Edge(Node target, TTString label) {
            this.target = target;
            this.label = label;
        }
    }

    protected static class Node {
        Edge[] edges;           // the children of this node
        int numberOfChildren;   // the number of children
        public Node() {
            edges = new Edge[128];
            numberOfChildren = 0;
        }
    }

    /**
     * number of strings stored in the trie
     */
    protected int number;

    /**
     * This is root
     */
    protected Node root;

    public PatriciaTrie() {
        root = new Node();
        number = 0;
    }

    /** 
     * Add the x to this trie
     * @param x the string to add
     * @return true if x was successfully added or false if x is already in the trie
     */
    public boolean insert(TTString x) {
        Node current = root;
        for (int i = 0; i < x.length(); i++) {
            TTString ch = x.subString(i, 1);
            if (current.edges[x.charAt(i)] != null) {
                Node child = current.edges[x.charAt(i)].target;
                current = child;
            } else {
                current.edges[x.charAt(i)] = new Edge(new Node(), ch);
                current.numberOfChildren++;
                current = current.edges[x.charAt(i)].target;
            }
            if (i == x.length() - 1)
                return true;
        }
        return false;
    }

    /** 
     * Remove x from this trie
     * @param x the string to remove
     * @return true if x was successfully removed or false if x is not stored in the trie
     */
    public boolean remove(TTString x) {
        // not sure how to do this

        return false;
    }       
}

And below is my TTString class -

public class TTString {
    int i;        // index of first character  
    int m;        // length
    byte[] data;  // data 

    public TTString(String s) {
        data = s.getBytes();
        i = 0;
        m = s.length();
    }

    protected TTString(byte[] data, int i, int m) {
        this.data = data;
        this.i = i;
        this.m = m;
    }

    public TTString subString(int j, int n) {
        if (j < 0 || j >= m) throw new IndexOutOfBoundsException();
        if (n < 0 || j + n > m) throw new IndexOutOfBoundsException();
        return new TTString(data, i+j, n);
    }

    /**
     * The length of this string
     * @return
     */
    public int length() {
        return m;
    }

    /**
     * Return the character at index j
     * @param j
     * @return
     */
    public char charAt(int j) {
        return (char)data[i+j];
    }
}

Any thoughts on how to implement remove method here?

Answer 1

One idea is: descend from the root to the leaf corresponding to the last character of x (assuming there is path containing x, otherwise there's nothing to change), remembering last fork on your path in the process (first fork is at the root). When you at the leaf, remove all edges/nodes from the last fork till the leaf.