2
$\begingroup$

I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it.

For example, to construct $k=1$ suppose $N$ is the number of nodes. If for each node $x$ ($\in 0..N-1$), we pick the child as (x+1) % N. Then picking any $r$ as the root, the tree remains the same structure except for there is no connection between $r-1$ and $r$ (modulo $N$). Each node has the same parent or no parent and has the same child or no child for all possible root.

For $k>2$ there is no such construct that I can find. Suppose just $k=2$ . If I arrange the binary in which $x$ has two children (x+1) % N and (x+2) % N. It doesn't give a correct tree with all the nodes anymore.

Another way is to do (((x-r)%N)*2+1 + r) % N and (((x-r)%N*2+2 + r) % N which gives a correct tree, but seems like there is $N$ possible choice of parent/child depending on root, the structure dramatically different all the times.

In other words, given an unknown root $r$, give $x$, it's still possible to know the possible connecting nodes (or bounded the number of connecting nodes < $O(N)$)


Another attempt to clarify this question -- an equivalent problem: I need to create a connected graph of out $N$ node, such that when given a node $r$, I can create a complete $k$-ary rooted by $r$ tree by removing some edges out of the graph. Obviously with a complete graph this is possible, can we create a graph in which each node connects to only $O(k)$ other nodes?

This works for $k$=1 with a line-graph.

$\endgroup$
  • $\begingroup$ Does your requirement mean that you need to create indexed inorder traversal on k-ary tree for any k? $\endgroup$ – Evil Jul 26 '17 at 23:33
  • $\begingroup$ It doesn't need to be in-order like 1-2-3-4-5.. but I want to be able to know deterministically the possible connected nodes without knowing the root of the tree. $\endgroup$ – w00d Jul 26 '17 at 23:41
  • $\begingroup$ It is not obvious to me what "wrap around" means. Why after picking some node it is no longer connected to r -1 and r + 1? Is it possible to create small example of tree behaviour for some fixed k? (I would opt for k > 3, including use case, dominant operations and expected runtime, but I have my suspicion that it should be optimised and this tree is probably graph or k-ary tree with some augmentation or additional indexing structure). If you can clarify then please remove "binary" tag as you want arbitrary k. $\endgroup$ – Evil Jul 26 '17 at 23:56
  • $\begingroup$ I don't understand what you are asking. Can you try to phrase your question differently? If for each $x$, node $x$'s child is $x+1 \bmod N$, then you have a boring tree (each node has exactly one child), and it's a $1$-ary tree. What does that have to do with $k$-ary trees for $k \ge 2$? You say you want a $k$-ary tree, where $k \ge 2$, then you start talking about the case $k=1$. I don't understand what's going on at all. What is your question? I encourage you to edit the question to define your requirements and your question more clearly. $\endgroup$ – D.W. Jul 26 '17 at 23:56
  • $\begingroup$ @D.W. I edited it several time, maybe you can check it again. The meaning is, I can construct the tree with property I wanted with k=1, but not $k\geq 2$. The property is that, the structure of the tree remains (parent/child links) and does not depend on the root you chose. $\endgroup$ – w00d Jul 27 '17 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.