Monday, October 18, 2010

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.

No comments: