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$.
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.
Best Answer
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$.