Compute index for leafs in a tree structure

Question

Given a tree (binary) structure, with depth N. Is it possible to compute some lookup index for mapping leaf nodes.

Each node knows its parent, and its childs(left and right) if its not a leaf.

My Idea was something like saying rootnode is index 0, then left:1,left:left:2, left:left:left:3, left:left:right:4, left:right:left:5,left:right:right:6,right:7,right:left:8 e.g.

So given a leaf node, how can i compute the index smartest.

Other solutions are accepted also, if its smarter to give the leafs indexes from 0,1...L, where L is the number of leafs.

Answer 1

If you wish to represent a tree in an array, the simplest is to take the layers of tree one at a time.

      0
     / \
    /   \
   1     2       [0, 1, 2, 3, 4, 5, 6]
  / \   / \
 3   4 5   6

This way, finding the parent is simply: (index-1)/2. And finding the two children is just 2*index and 2*index + 1.

Answer 2

In my Tree structure (Quadtree and Octree) I am using a binary representation of the indexes of each node. e.g. 32 bit (for max 32 level) for each dimension. So I can compute the complete index (or path) of a leaf by the formula

path.x = (unsigned int)(leaf.position.x * pow(2,32));

leaf.position.x musst be in a range from 0...1

The only constraint (I think) for this method is that the data you are storing musst be in a specific range, so that you can devide it by your area size. If this is possible for your usecase read more at Simple and Efficient Traversal Methods for Quadtrees and Octrees