§ Numbering nodes in a tree

If we consider a tree such as: 
      a
b         c
        d   e
The "standard way" of numbering, by starting with a 0 and then appending a 0 on going to the left, appending a 1 on going to the right doesn't make a great deal of sense. On the other hand, we can choose to number them as follows:
  • Consider the root to have value 1
  • Every time we go right, we add 1/2^{height}. When we go left, we subtract 1/2^{height}.
  • This gives us the numbers: 
      1
0.5       1.5
       1.25     1.75
  • This also makes intuitive why to find the node to replace 1.5 when we delete it is to go to the left child 1.25 and then travel as much to the right as possible. That path corresponds to:
1+1/2−1/4+1/8+1/16+…=1+1/2−1/4+1/4=1.5 \begin{aligned} &1 + 1/2 - 1/4 + 1/8 + 1/16 + \dots \\ &= 1 + 1/2 - 1/4 + 1/4 \\ &= 1.5 \end{aligned}
  • So in the limit, the rightmost leaf of the left child of the parent has the same value as the parent itself. In the non-limit, we get as close as possible.
  • This also may help intuit hyperbolic space? Distances as we go down in the three shrink. Thus, it's easier to "escape" away to the fringes of the space, rather than retrace your step. Recall that random walks in hyperbolic space almost surely move away from the point of origin. It feels to me like this explains why. If going towards the root / decreasing heighttakes distance dd, going deeper into the tree / increasing the height needs distance d/2d/2. So a particle would "tend to" travel the shorter distance.