Retina, 6969 55 bytes
The trailing linefeed is significant.
m`.(?<=(?=\D*^\1(?!\2))(?=\D*^\1\2)\A\D*^\D*^(.*)(.))|^.
:$&
T`w
O`
A-2`
Input is a linefeed-separated list.
Try it online! Performance can be increased significantly by inserting a \A before the last \D on the first line.
Explanation
A node is inserted into a word in three places:
- The beginning.
- After any longest prefix shared with another word. That is, a shared prefix after which the two words differ.
- The end.
In Retina, it tends to be shorter to produce N+1 when you've counted N things, so we're ignoring the one at the end. However, for the case of the empty input, we'll then also have to ignore the start, because beginning and end are the same.
To do the actual counting we insert : into every place where there is a node. Then we simply find the maximum number of : in a word and return that plus 1. Here is how the code does it:
m`.(?<=(?=\D*^\1(?!\2))\D*^(.*)(.))|^.
:$&
This detects all the nodes. It matches a character. Then it enters a lookbehind which captures that character into group 2 and the prefix before it into group 1. Then it goes all the way to the beginning of the string to start a lookahead, which checks that it can find the prefix somewhere where it's not followed by the captured character. If we find this match we insert a : in front of the character. We also match the first character of the current word to insert a : at the beginning of non-empty words.
T`w
This removes all the letters and leaves only the :.
O`
This sorts the lines, bringing the maximum depth to the end.
A-2`
This discards all but the last line.
And the empty line at the end counts the number of empty matches in that line, which is one more than the number of colons in it.
Try it online! (The first line enables a linefeed-separated test suite, where each test case uses comma separation instead.)