1 / 3 Tries & Prefix Structures

Nine Nodes Five Words

This trie holds cat, car, cart, do, dog. A dashed ring marks a node where a stored word ends.

Trie over cat, car, cart, do, dog with end-of-word nodes filled root cd a tr t og dashed ring = end-of-word

How many nodes does the trie contain (counting the root), and how many of them are marked as end-of-word?

A

15 nodes, 5 end-of-word

B

9 nodes, 5 end-of-word

C

9 nodes, 4 end-of-word

D

8 nodes, 5 end-of-word