Some confusion regarding the Binary tree Property about the Number of external nodes = Number of Internal Node + 1

Question

Everybody would agree that this one, shown below, is a valid Binary tree.

* (R)
 \
  \
   * (C)

The above binary tree node marked R, is the root and the node marked C is the child. This is not a Full binary tree, where in a node has exactly two childs or it has none. But the above one is a Binary tree.

In Binary tree, we have a property that the

|external nodes| = |internal nodes| + 1

that is, in words

The number of external nodes is one more than the number of internal nodes.

Where External Node is the node which has no child. Internal Node is the node which has either 1 or 2 child.

But the above tree shown in the diagram this property does not seem to hold ? Am I making some mistake in my understanding ?

Answer 1

According to the Fundamentals of Data Structures book by Ellis Horowitz and Sartaj Sahani.

For any nonempty binary tree, if A is the number of leaf nodes, and C is the number of nodes of degree 2, then A = C + 1

The degree of a node is the number of subtrees of that node. So if a node is having one child or equivalently one subtree, it's degree is 1, if the node is having two child or two subtrees then it's degree is 2 and if there are no children then it's degree is 0.

Lemma : For any nonempty binary tree T, if A is the number of leaf nodes, and C is the number of nodes of degree 2, then A = C + 1

Proof: Let B be the number of Nodes of degree 1 and N the total number of Nodes. Since all the nodes in Binary Tree T are at most degree 2, we have

            N = A + B + C  -------------(1)

If we count the edges in the binary tree, we find that there are N - 1 edges. That there are N - 1 edges follows from the fact that each edge connects some node to its parent, and every node except the root has one parent. Let E represent the edges then N = E + 1.

Also, since all branches stem from a node of degree 1 or 2. Thus, E = B + 2C

Hence, we obtain

             N = E + 1 = B + 2C + 1    --------(2)

Since N = A + B + C as well as N = B + 2C + 1, if we subtract B + 2C + 1 from A + B + C, that is if we do

      N - N = (A + B + C) - (B + 2C + 1) 

      0 = A - C - 1
      or A = C + 1;

But A is the number of leaf nodes and C is the nodes having 2 childs.

So this relation holds only in between nodes having no subtree or no child and those having 2 child or 2 subtrees.

And hence the scenario in the question :-

   * (R)
    \
     \
      * (C)

will not arise. As R is the node with 1 subtree and C is the leaf node. In fact for this kind of binary tree, as well, the above relation holds true, as there are no nodes with two subtree in the above binary tree in the diagram, that is nodes having 2 child is 0 here. And since there is one leaf node, the relation

     |Leaf Nodes| = |Nodes having 2 subtrees| + 1

expressed in the lemma holds.

To conclude the relationship holds between the nodes having two childs and nodes having no childs, and the relationship is

|External Nodes Or Leaf Nodes| = |Nodes having 2 subtrees Or 2 children| + 1