0
$\begingroup$

I am looking at the proof of this and I am so completely lost on where they are getting some of the expressions. Here is the proof:

Consider that $N$ is the number of nodes, $F$ is the number of full nodes, $L$ is the number of leaves in a tree, and $H$ is the height of the number of nodes with only one child or half-children. Then the total number of nodes in a binary tree is given as:

$N = F + L + H$

As, each full node is the incident of the two outgoing edges, thus each of the half nodes is called as the incident of one outgoing steps while each of the leaf nodes is the incident on no of outgoing edges that follows the total number of edges with in a binary tree is equal to $2F + H$. The total number of edges in a tree is equal to $N - 1$, hence,

$2F + H = N - 1 => H = N - 1 - 2F$

From there we substitute that value into $H$ and after solving we get $F + 1 = L$. The substituting part and everything I can do easily. The part I am so completely confused on is where and how they got $2F + H$. I don't understand that at all. I know a full node has 2 children, but I don't understand how that correlates to $2F + H$. Can someone help explain this?

$\endgroup$
0
$\begingroup$

The proof by induction on the number of nodes is much less complicated than this. It's obviously true for a single node with two children. Now suppose it's true when a tree has n nodes, and add an (n+1)th node to the tree. If its parent had no children before we added it, then the number of full nodes remains constant and the number of leaves remains constant, since the parent was a leaf before we added the new node and now the new node is a leaf. If the parent had one child beforehand, then the number of full nodes increases by 1 and the number of leaves increases by 1. This completes the proof.

$\endgroup$
0
$\begingroup$

They’re imagining each edge to be directed away from the root and towards the leaves, so that each edge has a ‘tail’ node (towards the root) and a ‘head’ nod (towards the leaves). We can count the edges by their tail nodes. Each full node is the tail node of $2$ edges, so there are $2F$ edges whose tail nodes are full nodes. Each half node is the tail node of $1$ edge, so there are $H$ edges whose tail nodes are half nodes. Putting the two together, we get a total of $2F+H$ edges. Since no edge has a leaf as its tail node, we’ve accounted for all of the edges: there really are $2F+H$ of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.