recursive definition of path length of a tree

Question

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.

The path length of a tree is the sum of the levels of all the tree's nodes. The path length can have simple recursive definition as follows.

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.

I am not able to follow above recursive defintion. Kindly explain with simple example.

Answer 1

Understanding the recursion

The path length can have simple recursive definition as follows.

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.

First, you have to understand what the path length is: It is the sum of all the distances between the nodes and the root.

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.

Let's assume we already know the path length of some trees. If we were to create a new node R, to which we connect all trees we already have, think about how the distances to the root node change.

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.

Thus, we add N - 1, because there are N - 1 descendants from the root node, which are now all one further from the root , and 1*(N-1) = N-1

---

You calculate the path length easily in several ways, you can either count the edges or the nodes.

Counting Nodes

             A        Level 0
           /   \      
          B     C     Level 1
         / \   / \
        D   E F   G   Level 2

We start with a path length of 0:

• Node A 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)
  • 0 + (0) = 0
• On level 1, you have two nodes: B and C:
  • 0 + (1 + 1) = 2
• On level 2, you have four nodes: D, E, F and G:
  • 2 + (2 + 2 + 2 + 2) = 10

Counting edges

             A        
           /   \      Level 1
          B     C     
         / \   / \    Level 2
        D   E F   G

• 0, our initial sum
• + 1*2 On level 1, there are 2 edges
• + 2*4 On level 2, there are 4 edges

Translating the definition into maths

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.

Let L_i denote the set of nodes on level i and h denote the height, i.e. maximum distance from a node to the root: