Question

Show that the external path length epl in a 2-tree with m external nodes satisfies epl≤ (1/2)(m^2+m−2). Conclude that epl≤ (1/2n)(n+ 3) for a 2-tree with n internal nodes.

Answer 1

Few terms related to given questions are defined as:

• External node is a node which is different from the rest of the tree.
• 2-tree is the tree where each node has 2 or more children.
• EPL stands for External path length. EPL is the sum of lengths of all the paths from root to any external node of a 2 tree. Here, length of path is considered as number of edges.

Now, it is known that m external nodes will have m-1 internal nodes. So, EPL_max is given as:

1 + 2 + - - - - - - - + (m-1) + (m-1)

EPL_max will become

Because sum of n natural numbers is n(n-1)/2.

Therefore, it can be concluded that for m external nodes in a 2 tree,

Now, we know that there are m-1 internal nodes, Lets denote internal nodes as n.

Therefore, n=m-1

                    m=n+1

Now, put m= n+1 in the derived value of EPL_max, we will get,

Therefore, it can be concluded that for a tree with n internal nodes,