Location: TB Homepage > Puzzles > Tree measures

Tree measures

Q: Consider a random finite rooted binary tree. Any given leaf can be reached by a unique shortest sequence of steps from the root. Suppose we pick a leaf uniformly at random, but then take only the first k of these steps from the root. We might reach the leaf we first thought of (maybe in fewer than k steps), or we might reach a node that's a parent of that leaf. Define:

How do these values vary with k, for a large tree? Do the functions approach each other for large k? Do we need to be more specific about what a "random" tree is?

This puzzle was inspired by a discussion of the resolution of my TORUS tune-indexing system, which includes graphs of these functions for the system's database tree.

This page is maintained by Thomas Bending, and was last modified on Thu 28 July 2022.
Comments, criticisms and suggestions are welcome. Copyright © Thomas Bending 2022