Trees and jumps and real roots

摘要

When the nodes of a tree are visited in depth-first order there are occasional jumps from a deeper level of the tree to a higher level. On the set of all full binary trees with a given number of nodes there is about 1 jump for every 2 internal nodes, and the average jump distance is about 2 levels. These averages are close to averages for trees that arise in polynomial real root isolation.