StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Understanding the recursion</h2> <blockquote> <p>The path length can have simple recursive definition as follows.</p> <p>The path length of a tree with N nodes is the sum of the path lengths of the subtrees of its root plus N-1.</p> </blockquote> <p>First, you have to understand what the path length is: It is the sum of all the distances between the nodes and the root.</p> <p>With this thought in mind, it is trivial to see that the path length for a root node without children is 0: There are no nodes with a distance to the root node.</p> <p>Let's assume we already know the path length of some trees. If we were to create a new node <code>R</code>, to which we connect all trees we already have, think about how the distances to the root node change.</p> <p>Previously, the distances were measured to the root of the trees (now subtrees). Now, there's one more step to be made to the root node, i.e. all distances increase by one.</p> <p>Thus, we add <code>N - 1</code>, because there are <code>N - 1</code> descendants from the root node, which are now all one further from the root , and <code>1*(N-1) = N-1</code></p> <hr> <p>You calculate the path length easily in several ways, you can either count the edges or the nodes.</p> <h2>Counting Nodes</h2> <pre><code> A Level 0 / \ B C Level 1 / \ / \ D E F G Level 2 </code></pre> <p>We start with a path length of 0:</p> <ul> <li>Node <code>A</code> is the root, which is always on level 0. It does not contribute to the path length. (You don't need to follow any paths to reach it, hence 0) <ul> <li><code>0 + (0) = 0</code></li> </ul></li> <li>On level 1, you have two nodes: <code>B</code> and <code>C</code>: <ul> <li><code>0 + (1 + 1) = 2</code></li> </ul></li> <li>On level 2, you have four nodes: <code>D, E, F</code> and <code>G</code>: <ul> <li><code>2 + (2 + 2 + 2 + 2) = 10</code></li> </ul></li> </ul> <h2>Counting edges</h2> <pre><code> A / \ Level 1 B C / \ / \ Level 2 D E F G </code></pre> <ul> <li><code>0</code>, our initial sum</li> <li><code>+ 1*2</code> On level <code>1</code>, there are <code>2</code> edges</li> <li><code>+ 2*4</code> On level <code>2</code>, there are <code>4</code> edges</li> </ul> <h2>Translating the definition into maths</h2> <blockquote> <p>A convinent way to compute the path length of a tree is to sum, for all k, the product of k and the umber of nodes at level k.</p> </blockquote> <p>Let L<sub>i</sub> denote the set of nodes on level <code>i</code> and <code>h</code> denote the height, i.e. maximum distance from a node to the root:</p> <p><img src="https://i.stack.imgur.com/ALpNo.gif" alt="enter image description here"></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload