The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$),

  1. $\leq n^{2}$ always.
  2. $\geq n \log_{2} n$ always.
  3. Equal to $n^{2}$ always.
  4. $O(n)$ for some special trees.
asked in DS by Veteran (42.9k points) | 139 views
D should be correct

3 Answers

0 votes
External node means leaf.

a binary tree has at most n/2 Leaves. Means at most or order n.

the length of path from root to leaf is at most log(n)

summing over all such nodes gives nlog(n) Lower bound. Option B

this can be always less than order n squared in the worst case. Option A.


option C is not possible because it can be less than that.

Option D is not possible because it is always greater than order n.
answered by (347 points)
0 votes
Here the question asked for binary tree

It can be of 2 types (1) skewed tree (2) Balanced binary tree or AVL tree

We have to find external path length i.e. leaf node

We also know cost of external path = leaf node value * lenth of path

Now for balanced tree external path length=$n\times log n$

But for skewed tree it will be $O\left ( n \right )$ only

So, ans will be D)
answered by Veteran (70.4k points)
–1 vote
I think A) and D)
answered by Active (1.1k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,138 questions
36,959 answers
34,802 users