- Forum
- General C++ Programming
- Binary Tree Question
Binary Tree Question
Hello,
I am lost trying to understand and answer the following question:
From what I've read so far, there is a theorem that states that an N-ary tree with n greater than or equal to 0 internal nodes contains (N - 1)n + 1 external nodes. And the proof states that if we let the number of external nodes be l, every node except the root has a parent, and there must be (n +1 - 1)/ N parents in the tree since every parent has N children. Therefore, n = (n + l -1) / N, which gives l = (N - 1) n + 1.
I am weak in math but what I did was this:
l = (N - 1) n + 1
l = N (squared) -n + 1
l - 1 = N (squared) - n
Any assistence will be greatly appreciated. Thanks in advance
I am lost trying to understand and answer the following question:
| A full node in a binary tree is a node with two non-empty subtrees. Let l be the number of leaf nodes in a binary tree. Show that the number of full nodes is l-1. |
From what I've read so far, there is a theorem that states that an N-ary tree with n greater than or equal to 0 internal nodes contains (N - 1)n + 1 external nodes. And the proof states that if we let the number of external nodes be l, every node except the root has a parent, and there must be (n +1 - 1)/ N parents in the tree since every parent has N children. Therefore, n = (n + l -1) / N, which gives l = (N - 1) n + 1.
I am weak in math but what I did was this:
l = (N - 1) n + 1
l = N (squared) -n + 1
l - 1 = N (squared) - n
Any assistence will be greatly appreciated. Thanks in advance
Well, N=2 in a binary tree so substituting N=2 in your last equation gives
L - 1 = 4 - n
L = 5 - n
which would seem to contradict the problem statement so your math mustn't be right.
L - 1 = 4 - n
L = 5 - n
which would seem to contradict the problem statement so your math mustn't be right.
Topic archived. No new replies allowed.