Internal Path Length of BST

Question

Consider the following binary tree with root at level 0. 

What is the internal path length for the above tree?

• A. 31
• B. 14
• C. 29
• D. 32

Comments

I am getting 30

Answer 1

First,let's define a node's path -length and internal path length of a tree:

A node's path length can be defined as no. of links(or edges) it needs to traverse to reach the root of the tree.And an internal node's path length($$I_{k},where\:I_{k}\:is\:path\:length\:of\:k^{th}\:internal\:node\:where\:k\in \left \{x:x\: is\:an\:internal\:node \right \}$$)is simply path length of any internal node of the tree.

Internal-path length(L) can be defined as a summation of path lengths of all internal nodes of a tree:-

or, L=$\sum I_{k},\forall k\in \left \{ x:x\:is\:an\:internal\:node \right \}$

Now,to calculate internal path length,let's traverse the graph in a BFS i.e level wise and compute path length of internal nodes which is just an edge away from the root,then calculate the nodes which are 2 edges away from the root and so on.

path_length_level_wise

 Please ignore the above table.I'm not able to delete it.

path_length_level_wise

Level	Nodes(k)	$\sum I_{k,l},\forall k \in level(l)$
0	{A}	0
1	{B,C}	1+1=2
2	{E,I,J}	2+2+2=6
3	{F,L}	3+3=6
	{A,B,C,E,I,J,F,L}	0+2+6+6=14

So, the answer is 14 or option(b)

Comments

Why didn't you calculated for D,G,K,M ?

---

D,G,K,M are leaf nodes,and not internal nodes,the question asks for path length of all Internal Nodes.I hope that answers your question. :)

---

Thank you so much for clarifying.