# Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori

Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at each node?

I seem to recall hearing of some proof, many years ago, K was best when set to Euler's number. Therefore in real applications if you must choose a single number you pick 3 children and the tree should end up closely balanced between depth and width. In other words, binary trees tend to be too deep, and 5-trees are "too wide".

Some searching of the 'net and reading some tree designs on Wikipedia has not proved fruitful but perhaps I am dreaming up a false memory?

• Can you be more precise in what you mean by "too wide" and "too deep"? What exactly are you trying to optimize, and why? – Yuval Filmus Feb 11 '15 at 1:40
• Search trees, or just any trees? Do you know B-trees? – Raphael Feb 11 '15 at 11:40
• Yuval: I talking about average node children as compared to total tree depth. My memory was one where depth was minimized without having large numbers of children per node. Does this mean avg children equal to depth? maybe? – RudeDude Feb 12 '15 at 14:57
• Raphael: I don't think I want to limit this to just search trees. The concept I recall focused on a phone menu system since you don't want to listen to 9 options on each level of the tree nor do you want to drill down through too many layers of the tree to reach your desired option. – RudeDude Feb 12 '15 at 15:39
• This is a reasonably related SE question cs.stackexchange.com/questions/47453/… – RudeDude Apr 21 '16 at 13:32

This sounds as follows.

• The answer is that the optimal number of children in a tree is $e$. What was "optimal" in the question?

One such question is as follows.

• Let us construct a tree of $N$ nodes. Imagine we arrange them into a perfect $K$-ary tree with $L$ levels of internal vertices. When we search over such tree, assume that the worst case is that we visit $K$ vertices in each of the $L$ internal levels, making the search $O (K \cdot L)$. What is the optimal $K$ as $N$ tends to infinity?

Here, we select $K$, and then $L$ is computed as $log_K N$.

When we think about it a bit, here is an arithmetic rephrase.

• We have a number $N$. We want to express some integer $M \ge N$ as a product of integers $S_1 \cdot S_2 \cdots S_L$ so that the sum $S_1 + S_2 + \ldots + S_L$ is minimal possible. When $N$ tends to infinity, what will be the sequence $\{S\}$?

The values $S_1, S_2, \ldots, S_L$ are the number of children at levels $1, 2, \ldots, L$, respectively. If we had a perfect $K$-ary tree, all our $S_i$ would be equal to $K$, but we lifted the restriction that they are all equal: the essence of the solution remains the same.

When we don't insist that $N$ and $S_i$ are integers, after performing some basic calculus, we can see that the optimal answer is to pick all $S_i$ close to $e$. Note that the closest integer to $e$ is $3$. So for the integer version, the optimal answers turn out to be of the following forms: $$(3 \cdot 3 \cdots 3)$$ $$(3 \cdot 3 \cdots 3) \cdot 2$$ $$(3 \cdot 3 \cdots 3) \cdot 2 \cdot 2$$

• Yes, thank you for this response. This is definitely the framing that it needed so that both my question and the answer are covered. – RudeDude Jun 29 '18 at 13:40

I found this paper that talks about size-balance k-ary trees. Maybe you'll find it helpful.

Paper citation:

CHA, S. (2012). On Complete and Size Balanced k-ary Tree Integer Sequences. INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND INFORMATICS, 6(2), 8-8. Retrieved April 14, 2015, from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.352.3650&rep=rep1&type=pdf

• Interesting paper. Kind of dense but might touch on what I'm talking about after further reading. The author focuses on integer sequences of these balanced trees but doesn't talk about the relation between node degree and depth. – RudeDude Feb 12 '15 at 15:36
• Can you summarize the key points from the paper? Can you edit the question to include a full citation to the paper, including title, authors, and where published, so we can find it again if the link dies? We tend not to like link-only answers, as they become useless if the link disappears -- and because we want to contribute new, useful content, not just be a link farm. – D.W. Apr 14 '15 at 0:11
• Hope it works for you! @D.W. – David Merinos Apr 14 '15 at 1:01

If we want to have same depth as width in the menu system, we will want to have a tree with $K$ nodes in each menu, and have have $K$ depth. If all the data resides on leaves then we need to solve $K^K \geq n > (K-1)^{K-1}$. We can solve this using Lambert function. Solving $x^x = y$.

• Is there a motivation why we'd want to have the same depth as width? Is the goal to minimize the total number of items that the user sees during a single interaction, or something? I'd expect that the total number of items the user has to see is $DW$, where $D$ is the depth and $W$ is the width. It's not clear why $D=W$ would be an optimal choice there -- is there a reason why that would be optimal? For instance, it seems like width $2$ and depth $K \lg K$ will be better than width $K$ and depth $K$ (product $2 K \lg K$ is smaller than product $K^2$). – D.W. Apr 9 '16 at 0:36
• @D.W. I went with my feeling. There is a whole lot of research done by the HCI people. There is a depth width tradeoff in designing menus. The issue is human understanding of the complexity of the menu and not the size, if I understand correctly. Please refer lap.umd.edu/poms/chapter8/chapter8.html and related matter. And I thought this is what OP wanted, again this is my guess. – Shreesh Apr 9 '16 at 14:57
• @Shreesh yeah I'm not being super great at generating a design spec here because I was mostly trying to recall a ghost of a memory. – RudeDude Apr 21 '16 at 12:44
• Sorry, premature enter key (some sites don't need the shift+enter). We want users (tree searches) to find the result as quickly as possible. When listening to a phone tree the list of items can take a long time to read (K children) but it can also take a long time to dig deep in the tree (the $N^{(1/K)}$ approximate depth). My weak recollection that this was presented as a phone tree optimization so the large number of children-per-node may have been the primary influence on search performance. – RudeDude Apr 21 '16 at 12:48