### Question

A perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order.

```
0
/ \
1 4
/ \ / \
2 3 5 6
```

Given the index (k) of a particular node, calculate its level.

### Solution

**This is a magical solution**. It divides the tree in the middle with number k decrease by 1 each time.

Beautiful, and hard to understand.

### Code

**not written by me**.

```
public int countLevel(TreeNode root, int k, int n) {
int level = 0;
while (k != 0) {
k--;
n = (n - 1) / 2;
k = k % n;
level++;
}
return level + 1;
}
```