Redirected
edited by
2,163 views
1 votes
1 votes

Consider a full binary tree with $n$ internal nodes, internal path length $I$, and external path length $e$. the internal length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf.

Which of the following is correct for the full binary tree?

  1. $e=i+n$
  2. $e=i+2n$
  3. $e=2i+n$
  4. $e=2n+i$
edited by

2 Answers

4 votes
4 votes

Consider the following full binary tree where number of internal nodes n = 3

Internal path length i = d(A) + d(B) + d(C) =  0 + 1 + 1 = 2

External path length e = d(D) + d(E) + d(F) + d(G) = 2 + 2 + 2 + 2 = 8

We can see that e = i + 2n = 2 + 2(3) = 8

You can verify this is true for any full binary tree.

e = i + 2n is the answer.

Reference for calculating depth of a node in a tree ~

https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

Answer:

Related questions

1 votes
1 votes
1 answer
1
Arjun asked Nov 5, 2017
541 views
Heap allocation is required for languages thatUse dynamic scope rulesSupport dynamic data structuresSupport recursionSupport recursion and dynamic data structures
1 votes
1 votes
2 answers
2
Arjun asked Nov 5, 2017
1,007 views
Match the following WINDOWS system calls and UNIX system calls with reference to process control and File manipulation. $$\begin{array}{llll} & \textbf{Windows} & & \text...
1 votes
1 votes
3 answers
3
Arjun asked Nov 5, 2017
839 views
Which of the following routing technique / techniques is/are used in distributed systems?Fixed RoutingVirtual RoutingDynamic Routing(a) only(a) and (b) only(c) onlyAll (a...