Tree equations

19, Oct, 2010

Given an N-ary tree and number of internal nodes (I), find leaf nodes in the tree. Question posted here.

I thought many people get confused while working with tree/graph related mathematics. I am providing two fundamental equations that help in understanding these equations.

In a tree with I internal nodes and L leaf nodes, the total number of nodes is sum of internal nodes and external (leaf) nodes, i.e.

T = I + L -----à 1

Assume, we are given with 3 poles (nodes). We need minimum two ropes (edges/branches in graph terminology) to connect them. Similarly, a tree with T nodes on total will have (T – 1) branches.

An N-ary tree with I internal nodes will have (N x I) branches. It is because, each internal node can have utmost N branches. We have the following relation with total nodes T,

T – 1 = (N x I) ------à 2

From the above two equations, it is clear that leaf nodes can be given by the following relation,

L = (N - 1) x I + 1

In a binary tree, N = 2, hence in a binary tree external nodes are always one more than the internal nodes.