Is there a name for this kind of binary tree?

Question

While working on a math problem the following tree structure came up:

    o
     \
      o
     /
    o
   / \
  o   o
 / \ /

It is a binary tree with the following constraints:

• all nodes except the root have a left child
• all left-child nodes have a right child
• none of the right-child nodes have a right-child

It also has the following emerging properties:

• The nodes are indexable:
  • the root node has index 0
  • for a given node indexed n, its left child has index 2n and right child n + 1

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

• the number of edges at each level matches the fibonacci sequence:

    o
     \    1
      o
     /    1
    o
   / \    2
  o   o
 / \ /    3 // Then will be 5, 8 etc... 

I would like to know more about this specific kind of tree, for example other emerging properties, what kind of problem it can help to solve or how is it typically used, but despite this seeming like a basic data structure I can't find any information on it. Searching for "fibonacci restricted tree" yields unrelated results such as Fibonacci Heaps.

Questions:

• Is there an accepted name for this specific kind of binary tree?
• What are some examples of usage of this kind of tree in computer science?

Answer 1

Just a quick association to your tree structures and Fibonacci numbers.

The numbering scheme and hence the tree structure seems related to the concept of exponentiation by squaring. The power of a number (or matrix) can be recursively computed as follows.

• $A^{2n} = A^n * A^n $
• $A^{2n+1} = A * A^{2n} $

In this formula you recognize the left and right branches of your trees.

Computer scientists usually learn this when they see the Fibonacci sequence in their programming course. Straightforward recursion of the Fibonacci numbers leads to an exponential number of recursive calls, much worse that computing the numbers iteratively from the bottom. The Fibonacci numbers can be computed using matrix squaring using the matrices $\left(\begin{array}{cc}1 & 1 \\ 1 & 0 \end{array}\right)^n = \left(\begin{array}{cc}F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{array}\right)$.

The depth of the nodes is sequence A014701 in the On-Line Encyclopedia of Integer Sequences, "Number of multiplications to compute n-th power by the Chandah-sutra method".