About remove algorithm in tries chapter 11

📚 Official Books Data Structures & Algorithms in Dart
,
1

Hi
In Chapter 11: Tries
the remove algorithm remove only last node that has no children.
for example remove cute after insert it remove only e node that has no children.
I suggest edit the for loop like this:

 // 3
  while (current.parent != null &&
        current.children.isEmpty &&
        !current.isTerminating) {
    //current.parent!.children[current.key!] = null; //comment this and add the bottom line
    current.parent?.children.remove(current.key);
    current = current.parent!;
  }
1 Like
2

Thank you for commenting. I think you’re right. Since a Map in Dart can contain a key-value pair where the value is null, it would be better to simply remove the pair rather than set the value to null. We might be able to enforce this by making the value non-nullable for the child. That is, change this:

Map<T, TrieNode<T>?> children = {};

to this:

Map<T, TrieNode<T>> children = {};

in the TrieNode definition class. I recommend this change if we ever publish an updated version of the book.

Thanks again for your idea.

1 Like