Applying a Logarithm to Navigate a Tree

Question

I had once known of a way to use logarithms to move from one leaf of a tree to the next "in-order" leaf of a tree. I think it involved taking a position value (rank?) of the "current" leaf and using it as a seed for a fresh traversal from the root down to the new target leaf - all the way using a log function test to determine whether to follow the right or left node down to the leaf.

I no longer recall how to exercise that technique. Can anyone re-introduce me?

I also don't recall if the technique required the tree to be balanced, or if it worked on n-trees or only binary trees. Any info would be appreciated.

Answer 1

Since you mentioned whether to go left or right, I'm going to assume you're talking about a binary tree specifically. In that case, I think you're right that there is a way. If your nodes are numbered left-to-right, top-to-bottom, starting with 1, then you can find the rank (depth in the tree) by taking the log2 of the node's number. To find that node again from the root, you can use the binary representation of the number, where 0 = left and 1 = right.

For example:

• n = 11

• 11 in binary is 1011

• We always ignore the first 1 since it's going to be there for every number (all nodes of rank n will be binary numbers with n+1 digits, with the first digit being 1). We're left with 011, which is saying from the root go left, then right, then right.

If you want to find the next in-order leaf, take the current leaf's number and add one, then traverse from the root using this method.

I believe this only works with balanced binary trees.

Answer 2

OK, this proposal requires more characters than I can fit into a comment box. Steven does not believe that knowing the depth of the node in the tree is useful. I think it is. I have been wrong in the past, and I'm sure I'll be wrong in the future, so I will try to explain how this idea works in an attempt to not be wrong in the present. If I am, I apologize ahead of time. I'm nearly certain I got it from one of my Algorithms and Datastructures courses, using the CLR book. Please excuse any slips in notation or nomenclature, I haven't studied this stuff in a while.

Quoting wikipedia, "a complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible."

We are considering a complete tree with any branching degree (where a binary tree has a branching degree of two). Also, we are considering our nodes to have a 'positional value' which is an ordering of the positional value (top to bottom, left to right) of the node.

Now, if we are given a positional value, we can find the node in the following fashion. Take the log_base_n of the positional value of the element we are looking for (floor of this, we want an integer). Traverse down from the root that many times, minus one. Now, start looking through all the children of the nodes at this level. Your node you are searching for will be in this set.

This is an attempt in explaining the additional part of the wikipedia definition:

"This depth is equal to the integer part of log2(n) where n 
 is the number of nodes on  the balanced tree. 

 Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). 

 Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). 

 Example 3: balanced tree with 5 nodes, log2(5) = 2.32 
 (depth of tree is 2 nodes)."

This is useful, because you can simply traverse down to this level and then start looking around. It is useful and important to know the depth your node is located on, so you can start looking there, instead of starting to look at the beginning. Unless you know what level of the tree you are on, you get to start looking at all the nodes sequentially.

That is why I think it is helpful to know the depth of the node we are searching for.

It is a little bit odd, since having the "positional value" is not something we normally care about in a tree. I can see why Steve thought of this in terms of an array, since positional value is inherent in arrays.

-Brian J. Stinar-

Answer 3

Case 1: Nodes have pointers to their parent

Starting from the node, traverse up the parent pointer until one with non-null right_child is found. Go to the right_child and traverse left_child as long as they are non-null.

Case 2: Nodes do not have pointers to the parent

Starting from the root, find the path to the node (including the root and the node). Then find the latest vertex (i.e. a node) in the path that has non-null right_child. Go the the right_child and traverse left_child as long as they are non-null.

In both cases, we traversing either up or down from the root to one of the nodes. The maximum of such traversal is in the order of the depth of the tree, hence logarithmic in the size of the nodes if the tree is balanced.

Answer 4

I think I've found the answer, or at least a facsimile.

Assume the tree nodes are numbered, starting at 1, top-down and left-to-right. Assume traversal begins at the root, and halts when it finds node X (which means the parent is linked to its children). Also, for quick reference, the base 2 logarithmic values for nodes 1 through 12 are:

log2(1) = 0.0
log2(2) = 1
log2(3) = 1.58
log2(4) = 2
log2(5) = 2.32     
log2(6) = 2.58     
log2(7) = 2.807
log2(8) = 3
log2(9) = 3.16
log2(10) = 3.32
log2(11) = 3.459
log2(12) = 3.58

The fractional portion represents a unique diagonal position (notice how nodes 3, 6, and 12 all have fractional portion 0.58). Also notice that every node belongs either to the left or right side of the tree, depending on whether the log fractional component is less or great than 0.5. Anecdotes aside, the algorithm for finding a node is then as follows:

• examine fractional portion, if it is less than .5, turn left. Else turn right.
• subtract one from the whole number portion of the log, stop if the value reaches zero.
• double the fractional portion, and start over.

So, for example, if node 11 is what you seek then you start by computing the log which is 3.459. Then...

1. 3-459 <=fraction less than .5: turn left and decrement whole number to 2.
2. 2-918 <=doubled fraction more than .5: turn right and decrement whole number to 1.
3. 1-836 <=doubling .918 gives 1.836: but only fractional part counts: turn right and dec prior whole number to 0. Done!!

With appropriate accomodations, the same technique appears to work for any balanced n-ary tree. For example, given a balanced ternary tree, the choice of following left, middle, or right edges is again based on the fractional portion of the log, as follows:

between 0.5-0.832: turn left  (a one-third fraction range)
between 0.17-0.49: turn right  (another one-third fraction range)
otherwise go down the middle.  (the last one-third range)

The algorithm is adjusted by multiplying the fractional portion by 3 instead of 2. Again, a quick reference for those who want to test this last statement:

log3(1) = 0.0
log3(2) = 0.63          
log3(3) = 1             
log3(4) = 1.26          
log3(5) = 1.46
log3(6) = 1.63
log3(7) = 1.77
log3(8) = 1.89          
log3(9) = 2

At this point I wonder if there is an even more concise way to express this whole "log-based top-down selection of a node." I'm interested if anyone knows...