How can I calculate the node level in a perfect binary tree from a first order depth index?

Question

I have 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.

(For example, in a tree with three levels, the root node has an index of 0, the first child has 1, the first child of the first child has 2, the second child of the first child has 3, the second is 4, the first child of the second child has 5, the second child of the second child has an index 6.

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

)

I know the size of the tree (number of nodes / maximum level), but only the index of a specific node, and I need to calculate its level (i.e. its distance to the root directory). How to do this most effectively?

Answer 1

let i is the index you are looking for and n is the total number of nodes.

This algorithm does what you want:

 level = 0 while i != 0 do i-- n = (n-1)/2 i = i%n level++ done 

0 is the root index, if i = 0 , then you are at a good level, otherwise you can remove the root and you will get two subtrees n = (n-1)/2 updates the number of nodes - this is a new tree (which is a subtree of the old one) and i = i%n selects only a good subtree.

Answer 2

Here is another suggestion that will facilitate the solution of this issue:

If you mark nodes by index in width order, you can calculate the level without going around O (1) times. Therefore, if you are doing multiple requests, you can do O (N) BFT and get each request for O (1).

Formula for level:

 level = floor(log(index + 1)) 

Where is the magazine located at base 2

Try this tree:

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

Greetings.

Answer 3

It seems that walking on a tree itself should be quite effective.

At each step of the algorithm, consider the range of indices on the subtree node you are on. The first value of the range is the root of the node, and after that, the first half is the range of the subtree on the left, and the second half should be the range of the right subtree. Then you can recursively go down until you find your node.

For example, allows you to search in a level 4 tree with 15 elements

  (root node)(left elements)(right elements) Starting range: (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14) Go left : (1)(2 3 4)(5 6 7) Go right : (5)(6)(7) Found node, total depth 2 

You should be able to do this with a simple loop, using only a couple of variables to store the start and end of the ranges. You can also easily adapt this if you are making some minor changes, for example using post / pre / in-order traversal or starting indexes of form 1 instead of 0.

Answer 4

Unverified:

 int LevelFromIndex( int index, int count) { if (index == 0) return 0; if (index > (count - 1)/ 2) index -= (count - 1) / 2; return 1 + LevelFromIndex( index - 1, (count - 1) / 2); } 

Here count is the total number of nodes in the tree.

Answer 5

EDIT: Attempt number 1 ... only works for BFS.

If by an ideal binary tree you mean a binary tree with a bunch of similar structure, then you can calculate the parent index node using this formula:

 parentIndex = (index-1)/2 

So, you can repeat this formula until you reach <= 0, every time you loop, you essentially go up a level in the tree.

EDIT: Attempt number 2 ..

The best way I can come up with would be O (index + log n), which is O (n). Do DFS until you reach the index you want, then continue up the tree using the parent pointer until you reach the root, tracking the number of times you went up. This assumes that a parent pointer exists on each node.

Answer 6

If you have an index, you cannot find the depth.

Suppose you have a tree:

  1 / \ 2 5 / \ 3 4 

node with index 3 has a depth of 2.

Suppose you have a tree:

  1 / \ 2 3 / \ 4 5 

node with index 3 has a depth of 1.

You cannot distinguish between these two trees, knowing their indices. There is no way to find the distance from the root simply by knowing the index.

Edit: if you mean a perfect binary tree, as in, all the leaves are at the same depth, and each parent has two children, then you still cannot find the depth.

Compare these two trees:

  1 / \ 2 3 1 / \ 2 5 / \ / \ 3 4 6 7 

The depth of node 3 varies depending on the height of the tree.

Edit 2: if you know the height of the whole tree, you can use this recursive algorithm:

 def distanceFromRoot(index, rootIndex, treeHeight): if index == rootIndex: return 0 leftIndex = rootIndex+1 rightIndex = rootIndex + 2**treeHeight if index >= rightIndex: return 1 + distanceFromRoot(index, rightIndex, treeHeight-1) else: return 1 + distanceFromRoot(index, leftIndex, treeHeight-1) 

Answer 7

So, we have such a tree with 4 levels:

  0 - 0th level / \ 1 8 - 1th level / \ / \ 2 5 9 12 - 2th level / \ /\ / \ / \ 3 4 6 7 10 11 13 14 - 3th level 

As you can see, each left child has a root index increased by one (left = root + 1), because in DFS the left child always visits the first. The second node has an index on the left of the node, increased in size to the left subtree (right = left + leftSize). If we know the depth of the tree, we can calculate its size (size = 2 ^ depth - 1). Since the left subtree has a depth equal to the depth of the parent, reduced by one, its size = 2 ^ (parentDepth - 1) - 1.

So, now we have an algorithm - calculate the index on the left node, calculate the index on the right node. If there is a node index between it, go to the left node, else go to the right node.

the code:

 static int level(int index, int root, int treeDepth) { if (index == root) return 0; if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */) throw new Exception("Unable to find node"); int left = root + 1; int right = left + (int)Math.Pow(2, treeDepth - 1) - 1; if (index == left || index == right) return 1; if (left < index && index < right) return 1 + level(index, left, treeDepth - 1); else return 1 + level(index, right, treeDepth - 1); }