### sayeef006's blog

By sayeef006, history, 14 months ago,

Can we estimate the upper bound of number of nodes of a trie? I'm using the array based implementation of trie, so i have to declare an array with the highest number of nodes, i know when inserting 32bit numbers the node count cant be greater than (N*32), but the actual upper bound should be way less right? Because for each node there are only two options for the next node? Am I right on this and if i am, can we estimate that value?

• +12

| Write comment?
 » 14 months ago, # |   0 Doesn't single insertion require 32 nodes? But for random insertions I don't know the expected value.
 » 14 months ago, # |   0 I think that this construction is optimal: Greedy construction for 4 bits1010 +4 0101 +4 1101 +3 0010 +3 1001 +2 0110 +2 1110 +2 0001 +2 1011 +1 0100 +1 1100 +1 0011 +1 1000 +1 0111 +1 1111 +1 0000 +1 Let's notice that the pattern of counts is $2, 2, 4, 8, 16, 32, 64, 128, 256$... So the answer is $2 * 32 + 2 * 31 + 4 * 30 + 8 * 29$... and so on while the sum of coefficients is less than $n$.
 » 14 months ago, # | ← Rev. 4 →   +3 Let's call the group of nodes which are at distance $x$ from the root 'level $x$' of the trie. In a binary tree, the number of nodes in level $x$ of the tree is at most $2^x$. Furthermore, in a trie, the number of nodes in any level is at most $N$.Hence, the maximum number of nodes needed is $\sum\limits_{x=0}^{31}min(2^x, N)$. For $N = 10^6$, this number is $13048575$. I believe it is also possible to construct a trie with this number of nodes. (Construct a complete binary tree of minimal height such that it contains N leaves, then extend each of these leaves in a chain until each leaf is at depth 31. Then assign labels to each edge.)