0
$\begingroup$

I need help in solving this problem, let's say we have given perfect binary tree, in perfect binary tree all nodes have the same distance starting from the root, and there are $n$ nodes such that $n+1$ is power of $2$. Here is example of perfect binary tree with depth of $4$.

Perfect binary tree Now we can say that all numbers have their indexes, and the node with number written on it is indexed as 1, node with number 4 is 2, node with number 12 is 3 etc...

Now let's say we have given only the number of index of the node, for example 10, and 10 has written the number 5 on itself, how can we find this in logarithmic or linear time?

I know that we can find the depth of the node in $O(log(N))$ but how can we find which number is written on it? And is there faster way to find the depth of node?

Thanks in advance.

$\endgroup$
5
  • $\begingroup$ Let me check my understanding. You always number nodes according to in-order traversal, but each node has a label that you want to know. For that you need to access the node starting from the root of the tree. $\endgroup$ Mar 28, 2017 at 20:17
  • $\begingroup$ Yes, I have given the number according to in-order traversal, but I want to find the label of the node, and if it is possible to find the depth of each in-order traversal or labeled node in constant time $\endgroup$ Mar 28, 2017 at 20:18
  • $\begingroup$ Have you looked at the heap data structure? Would that work for you? The numbering of the nodes is different, of course. Could you live with that? $\endgroup$ Mar 28, 2017 at 20:26
  • $\begingroup$ I don't need heap, it's too complicated for my case, since we can have nodes up to $10^{18}$ $\endgroup$ Mar 28, 2017 at 20:32
  • $\begingroup$ Heaps are extremely simple, but I'm sure I don't understand your problem. $\endgroup$ Mar 28, 2017 at 20:44

1 Answer 1

1
$\begingroup$

Let $D$ be the depth of the tree (for the purposes of this answer, we define the root as being at level $0$, its children being at level 1, etc. So this definition of depth will be off by one from the one you are using). If given a node at index $i$, we can find the depth by identifying the largest natural number $d$ such that $2^d \leq i$. So for example, the node at index $5$ would be at depth $2$ since $2^2 \leq 5$ but $2^3 > 5$.

Next, notice that the labels of the nodes at each level have an interesting pattern. The first node is always some power of $2$ and the difference in labels between consecutive nodes in that level is the "next" power of $2$.

Thus, the label of the node can be found with the following formula: $$2^{D-d}+(i-2^d)2^{D-d+1}$$

EDIT: If you want to find the depth given the label $l$, notice that the leaves are all odd numbers, the level above that has labels divisible by $2$ but not by $4$, etc. Using this information, we can find the depth by first identifying the largest natural number $n$ such that $2^n$ divides evenly into $l$. The depth of the node will be $D-n$.

$\endgroup$
2
  • $\begingroup$ Big thanks for your answer, and still if you can help me is it possible to find the depth of node if the label is known, for example node with label 7 has depth 4, node with label 4 has depth 2? $\endgroup$ Mar 28, 2017 at 20:38
  • $\begingroup$ @someone123123 No problem, I've edited my answer to address your other problem involving finding the depth given the label. Just as a reminder, my definition of depth is one-off from yours, so be sure to keep that in mind if you plan on implementing a solution of some sort). $\endgroup$
    – benguin
    Mar 28, 2017 at 20:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .