The Gateway to Computer Science Excellence
+15 votes
649 views
Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.
in DS by Veteran (52.2k points)
edited by | 649 views

2 Answers

+15 votes
Best answer

Base Case :- When we have just root then, there are no non leaf nodes. So No of leaves $= 1$, No of non leaf nodes is $= 0$. Base case holds.

Induction Hypothesis :- Assume that now for $k$ internal nodes we will have $k+1$ leaves.

Inducting on no of leaves, Now we add $2$ more leaves to this tree. One of $k+1$ leaf will become internal node. So now we will have $k+1$ internal node. No of leafs will be $K+ 1 - 1$ ($1$ leaf just became internal node) $+ 2$(New leafs) . So we proved that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

by Boss (41.6k points)
edited by
0
2-descendants mean ?
0

@set2018

Descendant: A node reachable by repeated proceeding from parent to child. So for every non-leaf node, we must be having two nodes which can be obtained by proceeding from parent to child.

Ref: https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees

0
A descendant of a node N is either N itself, a child of N, a child of a child of N and so on for any number of levels .. We say node N is an ancestor of node M if M is a descendant of N ...
0
@Puja Mishra..."A descendant of a node N is either N itself, ......"

Can we call a node a descendant of itself?
+5 votes
**descendents mean immediate child or no of node from that node to leaf ??

if immediate then :
let total n nodes are in binary tree.
2*non_leaf node  + 1 = total node
non leaf node = (total node -1)/2 = (n-1)/2
no of leaf node + no of nonleaf node = total node
no of leaf node + (n-1)/2 = n
no of leaf node = (n+1)/2
                            =  (n-1 + 2)/2
                            = (n - 1)/2 + 1
                            = no of non leaf node + 1
by Veteran (60.6k points)
0

Descendant: A node reachable by repeated proceeding from parent to child..

Ref: https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology_used_in_trees

0
Sir ,how this come "total node= 2*non_leaf node  + 1  "

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,616 answers
195,897 comments
102,355 users