How can I determine the depth of a node in a perfect/full binary tree(each node has either 2 or 0 leafs). The nodes are labeled by a post-order traversal of the tree. For example, in this tree:
Depth = 4
// 15
// 7 14
// 3 6 10 13
// 1 2 4 5 8 9 11 12
I would like to find the depth of a single node, given the total depth of the tree. The depth of each left most leaf is log(n+1)/log(2), but I don't know how to find an inner node's depth.
PS: My goal is to find the parent of each node and the parent of each right node is n+1 and the coresponding right node to a left one is n+(2^depth)-1. So I figure knowing the depth would be enough to find the parent.
Assuming the vertices of the full binary tree of height $h$ are numbered by $1, 2, \ldots, 2^h - 1$ in post-order, then you can recover the depth of a node (i.e., its distance from the root) by the following recursive formula:
$$ \operatorname{d}(k, h) = \begin{cases} 0 & \text{ if } k = 2^h - 1 \\ 1 + \operatorname{d}\Big(k - (2^{h-1}-1)\cdot k_{h-1}, h-1\Big) & \text{ otherwise} \end{cases} $$
where $k_{i}$ is the $i$'th digit in the binary expansion of $k$, that is, $$6_0 = 0, 6_1 = 1, 6_2 = 1, 6_3 = 0, 6_4 = 0, \ldots$$
I hope this helps $\ddot\smile$