Ask a Question

  1. Home
  2. Ask a Question
  3. Question Details
Doubts ?
Post a question
Ask Us

Categories

prove that for any non-empty binary tree T,if n0 is the number of leaves and n2 be the number of nodes having degree 2,then n0=n2+1

on 2010-12-05 19:16:35   by nancy   on Information Technology  1 answers

Sumitavo

on 2010-12-06 10:30:00  

let n, e be the total no. of nodes and edges of the binary tree respectively. let n0 = total no. of nodes with 0 children n1 = total n0. of nodes with 1 child n2 = total no. of nodes with 2 children therefore, n = n0 + n1 + n2......(1) again e= n-1.....................(2) also e = n1 + 2*n2...............(3) from (2) and (3) n-1=n1 + 2*n2 =>n=1 + n1 + 2*n2.............(4) from (1) and (4) n0 + n1 + n2 = 1 + n1 + 2*n2 =>n0=1 + n2... proved