# 5.2. Implementation

## Trie Node

Let us define a class, [`TrieNode`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/TrieNode.java):

{% code lineNumbers="true" %}

```java
public class TrieNode<T> {
    private final Map<Character, TrieNode<T>> children;
    private TrieNode<T> parent;
    private boolean end_state;
    private char key;
    private T value;

    public TrieNode(TrieNode<T> parent, char key) {
        children = new HashMap<>();
        setEndState(false);
        setParent(parent);
        setKey(key);
        setValue(null);
    }
}
```

{% endcode %}

* `L1`: the generic type `T` represents the type of `value` in `L6`.
* `L2`: [`Map`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Map.html) is used to store the children.
* `L4`: `true` if this node represents the last character of a certain word; otherwise, `false`.
* `L9`: [`HashMap`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/HashMap.html) gives the $$O(1)$$ complexity for searching a key.

> What other types of maps are implemented in Java?

Let us define getter methods:

{% code lineNumbers="true" %}

```java
public TrieNode<T> getParent() { return parent; }

public char getKey() { return key; }

public T getValue() { return value; }

public TrieNode<T> getChild(char key) { return children.get(key); }

/** @return the map whose keys and values are children's characters and nodes. */
public Map<Character, TrieNode<T>> getChildrenMap() {
    return children;
}
```

{% endcode %}

* `L10`: returns the map consisting of children's characters as keys and their nodes as values.

> Is there any risk of returning `this.children` in `L11`?

Let us then define setter methods:

{% code lineNumbers="true" %}

```java
public void setParent(TrieNode<T> node) { parent = node; }

public void setKey(char key) { this.key = key; }

public void setEndState(boolean endState) { end_state = endState; }

public T setValue(T value) {
    T tmp = this.value;
    this.value = value;
    return tmp;
}

public TrieNode<T> addChild(char key) {
    TrieNode<T> child = getChild(key);

    if (child == null) {
        child = new TrieNode<>(this, key);
        children.put(key, child);
    }

    return child;
}

public TrieNode<T> removeChild(char key) {
    return children.remove(key);
}
```

{% endcode %}

* `L7`: returns the previously assigned value of this node.
* `L13`: returns the child with the specific key if exists; otherwise, a new child with the key.

> What does the `removeChild()` method return if `key` does not exist in this node?

Finally, let us define checker methods:

{% code lineNumbers="true" %}

```java
public boolean isEndState() { return end_state; }

public boolean hasValue() { return value != null; }

public boolean hasChildren() { return !children.isEmpty(); }
```

{% endcode %}

* `L1`: returns `true` if this node represents the last character of a certain word; `false`.

## Trie

Let us create the class, [`Trie`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/trie/Trie.java):

{% code lineNumbers="true" %}

```java
public class Trie<T> {
    private final TrieNode<T> root;

    public Trie() {
        root = new TrieNode<>(null, (char)0);
    }

    public TrieNode<T> getRoot() { return root; }
}
```

{% endcode %}

* `L1`: defines a generic type `T` that can be any type.
* `L5`: initializes the root with the `null` character.

Let us define the `find()` method that takes a specific key in string and returns the node corresponding the last character of the key:

{% code lineNumbers="true" %}

```java
/** @return the node with the specific key if exists; otherwise, {@code null}. */
public TrieNode<T> find(String key) {
    TrieNode<T> node = root;

    for (char c : key.toCharArray()) {
        node = node.getChild(c);
        if (node == null) return null;
    }

    return node;
}
```

{% endcode %}

* `L5`: iterates through every character in the string.
* `L6`: finds the node whose key is the current character.
* `L7`: the child does not exist, implying that `key` is not introduced in this trie.

Given the `find()` method, let us define the `get()` method that takes a string key and returns the value of the node corresponding to the key in this trie:

{% code lineNumbers="true" %}

```java
public T get(String key) {
    TrieNode<T> node = find(key);
    return (node != null && node.isEndState()) ? node.getValue() : null;
}

public boolean contains(String key) {
    return get(key) != null;
}
```

{% endcode %}

* `L3`: checks if both the key exists and the key is a word.

We then define the put() method that inserts a key-value pair to the trie:

{% code lineNumbers="true" %}

```java
public T put(String key, T value) {
    TrieNode<T> node = root;

    for (char c : key.toCharArray())
        node = node.addChild(c);

    node.setEndState(true);
    return node.setValue(value);
}
```

{% endcode %}

* `L4-5`: iterates through all characters in the key and adds children as necessary.
* `L7`: sets the end state of the node corresponding the last character to `true`.
* `L8`: returns the value of the previously key if exists; otherwise, `null`.

> What does `node.addChild(c)` return if the child with the key `c` already exists?

The following demonstrates how the `put()` method works:

{% embed url="<https://www.slideshare.net/jchoi7s/tries-put>" %}

Finally, let us define the `remove()` method that removes all appropriate nodes corresponding to the key:

{% code lineNumbers="true" %}

```java
public boolean remove(String key) {
    TrieNode<T> node = find(key);

    if (node == null || !node.isEndState())
        return false;

    if (node.hasChildren()) {
        node.setEndState(false);
        return true;
    }

    TrieNode<T> parent = node.getParent();

    while (parent != null) {
        parent.removeChild(node.getKey());

        if (parent.hasChildren() || parent.isEndState())
            break;
        else {
            node = parent;
            parent = parent.getParent();
        }
    }

    return true;
}
```

{% endcode %}

* `L2`: retrieves the node corresponding to the last character in the key.
* `L4`: returns `false` the key does not exist or the key is not a word.
* `L7-10`: if the retrieved node has children, sets its end-state to `false` and returns `true`.
* `L12-23`: removes ancestors who have descendants only related to this key.

The following demonstrates how the `remove()` method works:

{% embed url="<https://www.slideshare.net/jchoi7s/tries-remove>" %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/tries/implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.