Implementing Radix Trie

2025-08-24

Trie data-structure

While reading the book, Let’s GO Further. In it we are using the HTTP routing using the httprouter package to make our API’s. The one of the benefit the author tell about this package is that it uses the Radix Trie for url path matching.

So, me being me, thought what is Radix Trie why not just build it? And woilaaa, here we are in the article and we are just going to do exactly that.

Implementing Trie Data Structure

Before, implementing the main talking point of our article, let’s get the basics and build the parent of the Radix Trie that is Trie(didn’t expect him to be here?).

The idea is simple with the Trie, its like a Binary Tree but it has many childrens, usually 26 (cause english has these many letters). And each node hold Two things 1) a letter, 2) is it a word?

This is best for data-structure that we may need on a string. Like autocomplitions?

The benefit that a Trie has over the Binary Tree is that it does not require any balancing algorithm.

Let’s create some test’s first defining what we want.

trie_test.go

1
package whatever
2

3
import (
4
    "testing"
5

6
    "github.com/stretchr/testify/assert"
7
)
8

9
func TestTrie(t *testing.T) {
10
    tr := NewTrie()
11

12
    for _, w := range []string{"go", "gopher", "Game", "goal"} {
13
        err := tr.Insert(w)
14
        assert.NoError(t, err)
15
    }
16

17
  for _, want := range []string{"go", "gopher", "game", "goal"} {
18
    err := tr.Search(want)
19
    assert.NoError(t, err)
20
  }
21

22
  err := tr.Search("ghost")
23
  assert.ErrorIs(t, err, ds.ErrNoSuchWord)
24

25
  err = tr.Search("g")
26
  assert.ErrorIs(t, err, ds.ErrNoSuchWord)
27

28
  // Deletion & Search
29
  err = tr.Delete("go")
30
  assert.NoError(t, err)
31

32
  err = tr.Search("go")
33
  assert.ErrorIs(t, err, ds.ErrNoSuchWord)
34

35
  err = tr.Delete("gopher")
36
  assert.NoError(t, err)
37

38
  err = tr.Search("gopher")
39
  assert.ErrorIs(t, err, ds.ErrNoSuchWord)
40

41
  err = tr.Search("game")
42
  assert.NoError(t, err)
43
  err = tr.Search("Goal")
44
  assert.NoError(t, err)
45

46
  err = tr.Delete("carbon")
47
  assert.ErrorIs(t, err, ds.ErrNoSuchWord)
48
}

We will create the structure’s that will hold the values. So we want a node thingy that will hold

value,
children pointers,
parent for tranversing up, and
is flag that will tell if it is a word or nah.

Then the main trie, that will have a root, with no value in it.

We will also define the error types, its optional, if you want you can choose not return errors.

trie.go

1
package whatever
2

3
import (
4
    "error"
5
)
6

7
// defining all the error types that we would want to return
8
var (
9
  ErrNoSuchWord  = errors.New("no such word in trie")
10
  ErrNotWord     = errors.New("not word")
11
  ErrEmptyWord   = errors.New("empty word")
12
  ErrInvalidRune = errors.New("invalid character")
13
)
14

15

16
type trieNode struct {
17
    value    rune
18
    children [26]*trieNode
19
    parent   *trieNode
20
    isWord   bool
21
}
22

23
func NewTrieNode(val rune) *trieNode {
24
    return &trieNode{value: val}
25
}
26

27
type Trie struct {
28
    head *trieNode
29
}
30

31
func NewTrie() *Trie {
32
    var r rune
33
    return &Trie{head: NewTrieNode(r)}
34
}
35

36
// a helper function to get the index value
37
// will be helpful
38
func getIndex(r rune) (int, error) {
39
  if r < 'a' || r > 'z' {
40
    return -1, ErrInvalidRune
41
  }
42
  return int(r - 'a'), nil
43
}

The first method we would want to build is Search. The algo will go like this

Traverse the given word,
Check if the character is present in the trie, if it is then we move onto that, and
If the character is not present, then the word is not in the trie and return error.

Lastly, if every thing goes well we will be at the word’s last character node. Now if it is not a word return error else nothing.

1
import (
2
    "error"
3
   "strings"
4
)

1
func (t *Trie) Search(word string) error {
2
    if word == "" {
3
        return ErrEmptyWord
4
    }
5

6
    cur := t.head
7
    for _, r := range strings.ToLower(word) {
8
        idx, err := getIndex(r)
9
        if err != nil {
10
            return err
11
        }
12

13
        child := cur.children[idx]
14
        if child == nil {
15
            return ErrNoSuchWord
16
            }
17
        }
18
        cur = child
19
    }
20

21
    if cur.isWord {
22
        return nil
23
    }
24
    return ErrNoSuchWord
25
}

Now, let’s get to the Insert method. It’s simple, we want

To traverse the word,
If the character is present in the trie cool, we move to the next character,
If not then we create a new trie node, and move on

Lastly, we will set the word flag to be true.

1
func (t *Trie) Insert(word string) error {
2
    if word == "" {
3
        return ErrEmptyWord
4
    }
5
    cur := t.head
6

7
    for _, r := range strings.ToLower(word) {
8
        idx, err := getIndex(r)
9
        if err != nil {
10
            return err
11
        }
12

13
        child := cur.children[idx]
14
        if child == nil {
15
            child = NewTrieNode(r)
16
            child.parent = cur
17
            cur.children[idx] = chil
18
        }
19
        cur = child
20
    }
21
    cur.isWord = true
22
    return nil
23
}

The last method Delete, things we want to

traverse to the bottom of the trie, if we cannot that means the word is not in the trie, return err
check if the last node is a word, if not return error it is not a word, if it is true then mark it false
now, traverse up remove the node.

1
func (t *Trie) Delete(word string) error {
2
  if word == "" {
3
    return ErrNotWord
4
  }
5

6
  cur := t.head
7
  for _, r := range strings.ToLower(word) {
8
    idx, err := getIndex(r)
9
    if err != nil {
10
      return err
11
    }
12

13
    child := cur.children[idx]
14
    if child == nil {
15
      return ErrNoSuchWord
16
    }
17
    cur = child
18
  }
19

20
  if !cur.isWord {
21
    return ErrNotWord
22
  }
23
  cur.isWord = false
24

25
  parent := cur.parent
26
  for parent != nil {
27
    if t.hasChildren(parent) || cur.isWord {
28
      break
29
    }
30
    idx, err := getIndex(cur.value)
31
    if err != nil {
32
      return err
33
    }
34

35
    parent.children[idx] = nil
36
    cur = parent
37
    parent = parent.parent
38
  }
39
  return nil
40
}
41

42
func (t *Trie) hasChildren(parent *trieNode) bool {
43
  count := 0
44
  for _, pointer := range parent.children {
45
    if pointer != nil {
46
      count++
47
    }
48
  }
49
  if count > 1 {
50
    return true
51
  }
52
  return false
53
}

We done with our Trie implementation, now run the test, we should be passing all these tests.

Implementing Radix Trie Data Structure

Now to the main, agenda of the day. The normal Trie has one problem, it is not very space efficient. It creates node for every letter of the word.

That’s where the Radix Trie comes in. Radix Trie compact the words. Let’s see an example with a beautiful ascii art.

1
            RO OT
2
              |
3
            /   \
4
       bankai    wa
5
                /  \
6
              ste   t
7
                   / \
8
                  ch  er

Here we have the words bankai, water, waste, watch. The word bankai is present as a whole word in the trie. The latter words a split wa, ste, t, ch, er. All the last nodes are marked as words.

Let’s get started with the strucuture.

we want an edge that will have the label and the next node,
the node that will have isWord flag, hashmap with key as character and the value with the edge,
lastly, the main trie structure.

You can create the tests, like we did above.

radix.go

1
package whatever
2

3
type rdxE struct {
4
    label string
5
    next  *rdxN
6
}
7

8
func newRdxE(label string ) *rdxE {
9
    return &rdxE{label: label, next: newRdxNode(false)}
10
}
11

12
func newRdxEWithNext(label string, next *rdxN) *rdxE {
13
    return &rdxE{label: label, next: next}
14
}
15

16
type rdxN struct {
17
    edge   map[rune]*rdxE
18
    isWord bool
19
}
20

21
func newRdxNode(isWord bool) *rdxN {
22
    return &rdxN{edges: make(map[rune]*rdxE), isWord: isWord}
23
}
24

25
func (r *rdxN) addEdge(label string) {
26
    r.edges[rune(label[0])] = newRdxE(label)
27
}
28

29
func (r *rdxN) addEdgeWithNext(label string, next *rdxN) {
30
    r.edges[rune(label[0])] = newRdxEWithNext(label, next)
31
}
32

33
func (r *rdxN) getTransition(transitionChar rune) *rdxE {
34
  return r.edges[transitionChar]
35
}
36

37
type RdxTrie struct {
38
    root *rdxN
39
}
40

41
func NewRadixTrie() *RdxTrie {
42
    return &RdxTrie{root: newRdxNode(false)}
43
}

The node will have edge’s map as rune -> edge, and isWord flag tells whether upto this word it is a word. The edge will have the label, that will have the compact word if possible and the pointer to the next node.

The basic function Insert, Search & Delete. We separate the these because we are going to use the recursion (whoa… that scared me). It’s is a best idea to make a new function which will do the recursion for us (that’s what I’ve heard).

1
func (r *RdxTrie) Search(word string) bool {
2
  return r.search(r.root, word)
3
}
4

5
func (r *RdxTrie) Insert(word string) error {
6
  if word == "" {
7
    return ErrEmptyWord
8
  }
9
  r.insert(r.root, word)
10
  return nil
11
}
12

13
func (r *RdxTrie) Delete(word string) {
14
  r.delete(r.root, word)
15
}

Firstly, the Search. The Idea

get edge with the first character of the searching word
if the edge is null, return false
if the edge label does match the prefix of the searching word
if the edge label and the word match AND it is a word, return true
cut the prefix, then recurse with the cutted word, and the next node.

Let’s see it in action

1
func getRuneAt(word string, idx int) rune {
2
  return rune(word[idx])
3
}
4

5
func (r *RdxTrie) search(cur *rdxN, word string) bool {
6
    // base case
7
    if word == "" {
8
        return cur.isWord
9
    }
10

11
    transistionChar := getRuneAt(word, 0)
12
    childEdge := cur.getTransition(transitionChar)
13

14
    if childEdge == nil {
15
        return false
16
    }
17

18
    if !strings.HasPrefix(word, childEdge.label) {
19
        return false
20
    }
21

22
    after, found := strings.CutPrefix(word, childEdge.label)
23
    if !found {
24
        return false
25
    }
26

27
    return r.search(childEdge.next, after)
28
}

Now, for the Insert method. There are mutlitple case.

The word is not present in the trie, so simply add,
We want to add the word, and its prefix is present(e.g. word to be added “slower”, “slow” already present),
The opposite of the 2 (e.g. “slower” is present, want to add “slow”)
The word to be added and the word in the tree share the prefix (e.g. adding “waste”, and “water” is present)
The word is already present, mark it as word.

1
func (r *RadixTrie) commonPrefix(s1, s2 string) int {
2
  if len(s1) < 1 || len(s2) < 1 {
3
    return -1
4
  }
5
  minLen := min(len(s1), len(s2))
6
  cmnPreLen := -1
7

8
  for i := range minLen {
9
    if s1[i] != s2[i] {
10
      break
11
    }
12
    cmnPreLen++
13
  }
14

15
  return cmnPreLen
16
}
17

18
func (r *RdxTrie) insert(curr *rdxN, word string) {
19
    if word == "" {
20
        return
21
    }
22

23
    transitionChar := getRuneAt(word, 0)
24
    childEdge := curr.getTransistion(transitionChar)
25

26
    // case 1: word not present in the trie
27
    if childEdge == nil {
28
        curr.addEdge(word)
29
    childEdge = curr.getTransition(transitionChar)
30
    childEdge.next.isWord = true
31

32
    return
33
    }
34

35
  // Case 5: the word is already present as a label
36
  if word == childEdge.label {
37
    childEdge.next.isWord = true
38
    return
39
  }
40

41
  cmnPreIdx := r.commonPrefix(word, childEdge.label)
42

43
  // Case 2: adding word "slower", "slow" is present
44
  if cmnPreIdx+1 == len(childEdge.label) {
45
    suffix := word[cmnPreIdx+1:]
46
    r.insert(childEdge.next, suffix)
47
    return
48
  }
49

50
  // Case 3: adding word "slow", "slower" is present
51
  if cmnPreIdx+1 == len(word) {
52
    prefix := word[:cmnPreIdx+1]
53
    suffix := childEdge.label[cmnPreIdx+1:]
54
    delete(curr.edges, transitionChar)
55
    // add the prefix word
56
    curr.addEdge(prefix)
57
    newChildEdge := curr.getTransition(transitionChar)
58
    newChildEdge.next.isWord = true
59
    // recursive call
60
    r.insert(newChildEdge.next, suffix)
61
    return
62
  }
63

64
  // Case 4: adding word "waste", "water" is present
65
  // so the common Prefix idx len will not be equal to
66
  // the label or the word itself
67
  prefix := word[:cmnPreIdx+1]
68
  wordSuffix := word[cmnPreIdx+1:]
69
  labelSuffix := childEdge.label[cmnPreIdx+1:]
70
  delete(curr.edges, transitionChar)
71
  // add the prefix word
72
  curr.addEdge(prefix)
73
  newChildEdge := curr.getTransition(transitionChar)
74
  // if the prefix itself is a complete word
75
  if len(wordSuffix) == 0 {
76
    newChildEdge.next.isWord = true
77
  }
78
  // reatach the old label suffix under the new prefix
79
  newChildEdge.next.addEdgeWithNext(labelSuffix, childEdge.next)
80
  // add the new word's suffix
81
  if len(wordSuffix) > 0 {
82
    newChildEdge.next.addEdge(wordSuffix)
83
    newChildEdge.next.getTransition(getRuneAt(wordSuffix, 0)).next.isWord = true
84
  }
85

86
}

Now, the Delete, we want to traverse and get to the end word, and on the way back up want to remove uncessary nodes.

1
func (r *RadixTrie) delete(cur *rdxN, word string) *rdxN {
2
  if word == "" {
3
    return nil
4
  }
5

6
  transitionChar := getRuneAt(word, 0)
7
  edge := cur.getTransition(transitionChar)
8

9
  if edge == nil {
10
    return nil
11
  }
12

13
  if edge.label == word {
14
    edge.next.isWord = false
15
    return cur
16
  }
17

18
  cmnPrefix := r.commonPrefix(word, edge.label)
19
  suffix := word[cmnPrefix+1:]
20

21
  del := r.delete(edge.next, suffix)
22
  if del != nil {
23
    delete(cur.edges, getRuneAt(suffix, 0))
24
  }
25

26
  return cur
27
}

And know, we are done with our Radix Trie implementation.

Do check the implementation, and let me know if there is any edge case that I might be missing.

Afterwords

After days of smashing my head, I got the gist of implementing the Radix Trie.

Just know this,

Reinvent the wheel, so that you can learn how to invent wheel

– a nobody

References

Opengenus Radix Trie
Opengenus Trie
Google
ChatGPT (for some edge cases, that might have missed.)

#data-structures

#go