GATE1993-16

15 votes
928 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
edited

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.

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.

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?
7 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
0

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

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

Related questions

7 votes
3 answers
1
1.2k views
Consider a singly linked list having $n$ nodes. The data items $d_1, d_2, \dots d_n$ are stored in these $n$ nodes. Let $X$ be a pointer to the $j^{th}$ node $(1 \leq j \leq n)$ in which $d_j$ is stored. A new data item $d$ ... algorithm to insert $d$ into the list to obtain a list having items $d_1, d_2, \dots, d_{j}, d,\dots, d_n$ in order without using the header.
15 votes
2 answers
2
1.7k views
The following Pascal program segments finds the largest number in a two-dimensional integer array $A[0\dots n-1, 0\dots n-1]$ using a single loop. Fill up the boxes to complete the program and write against $\fbox{A}, \fbox{B}, \fbox{C} \text{ and } \fbox{D}$ in your answer book Assume that max is ... begin if A[i, j]>max then max:=A[i, j]; if |C| then j:=j+1; else begin j:=0; i:=|D| end end end
16 votes
3 answers
3
1.6k views
A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance of a node from the root is the length of the path from the root to the node. The height of a ... tree of height $h \geqslant 1$, how many nodes are at distance $h-1$ from the root? Write only the answer without any explanations.
31 votes
2 answers
4
5.3k views
Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true? LASTIN = LASTPOST LASTIN = LASTPRE LASTPRE = LASTPOST None of the above