The problem of describing trees

When I finished writing about the Zeno wagering game recently, I had some trees left over, so I thought I would try planting them here.

In the Zeno article I was trying to understand and explain the structure of this peculiar-looking tree, which I’ll call the tangled tree:

As a warmup exercise, I started out with this simpler example, the combed tree:

These are both binary trees: Each node has exactly two descendants. And the trees also share a basic internal symmetry. In both structures, if a node has horizontal coordinate x, the two descendant nodes are symmetrically arrayed at x-d and x+d. The difference between the two trees is all in how the displacement distance d is calculated. In the combed tree, d has the initial value 1/4 at the root node, and it is reduced by half at each lower level of the tree. In the tangled tree, the formula is d = 1/2 min(x, 1-x). In other words, d is half the distance to the nearer boundary of the interval [0,1].

There was a third tree I didn’t have room to include in the article. I had stumbled upon it when I made a programming error. This rogue structure looks like this, and I’m calling it the braided tree:

The nature of my programming error is not hard to see. Intending to generate the tangled tree, I had meant to calculate the positions of the child nodes as follows:

      left = x - 1/2 min(x, 1 - x)
      right = x + 1/2 min(x, 1 - x)

But instead I carelessly wrote:

      left = x - 1/2 x
      right = x + 1/2 (1 - x)

Stupid goof, but the result is visually intriguing. And although the braided tree is a botched version of the tangled tree, it actually has a lot in common with the combed tree. In particular, both the combed and the braided trees have exactly the same set of nodes; the difference is that those nodes are wired differently.

One way to understand the difference is to look at the paths leading from the root to any given node. Each such path is a sequence of left and right turns. For example, in the combed tree you can get from the root to the node at x = 3/16 by turning left at the root, then left again at 1/4 and finally right at 1/8. In the braided tree the path to 3/16 goes right to 3/4 then left to 3/8 and left to 3/16. Paths of this kind can be encoded as binary numerals, letting a 0 stand for each left turn and a 1 for each right turn. In this scheme the two paths described above are 001 and 100.

In essence, the braided tree is a permutation of the combed tree. If you list all the nodes at some fixed level in the combed tree (say those three levels below the root, where all denominators are 16), then the corresponding paths are in numerical order:

    1/16    000    (0)
    3/16    001    (1)
    5/16    010    (2)
    7/16    011    (3)
    9/16    100    (4)
   11/16    101    (5)
   13/16    110    (6)
   15/16    111    (7)

Here’s the corresponding tabulation for the braided tree:

    1/16    000    (0)
    3/16    100    (4)
    5/16    010    (2)
    7/16    110    (6)
    9/16    001    (1)
   11/16    101    (5)
   13/16    011    (3)
   15/16    111    (7)

The order is “counting from the left,” incrementing the most significant bit first. I wonder what other permutations give interesting-looking trees.

Turning back to the tangled tree that began this whole investigation, I would argue that it looks tangled and unruly not so much because lots of edges cross (there are even more crossings in the braided tree) but because of many near collisions and coincidences. For example, just below the root of the tangled tree, the mirror-image paths <left-right-right> and <right-left-left> almost converge on the same value, but they miss by just a bit. We can fix this! All it takes is an adjustment in the formula for the displacement d. In the tangled tree that displacement is 1/2 min(x, 1-x). The constant 1/2 in this expression is quite arbitrary, and we can substitute any other value a, with 0 < a < 1.

So what is the magic value of a in the following tree, which I am inclined to call the crocheted tree?

Note: If the title of this post fails to ring a bell, see the poem by Robert Hass:

The gene pool threw up a wobbly stem
And the tree danced. No.
The tree capitalized.
No. There are limits to saying,
In language, what the tree did.