
354 Data Structures Using C
This can be formally defined as:
Where L
i
: is the path length of internal node i
From induction , we can say that : L
EXT
= L
INT
+ 2 * N, where N is number of internal nodes.
In EBT of Figure 7.49, N = 6, therefore, L
EXT
= L
INT
+ 2 * N = 8 + 2 * 6 = 20.
Weighted Binary Tree: So far we have considered the cost of an edge between two nodes as one unit. In
real world the edges may differ in terms of length, weight, degree of comfort, profit, utility etc. However,
in order to keep things simpler, let us
keep the cost between each edge as one
but assign a weight W
i
to an ith external
node as shown in Figur