Problem 5. (25 points) The set of binary trees is defined inductively as follows
ID: 3283038 • Letter: P
Question
Problem 5. (25 points) The set of binary trees is defined inductively as follows: i. A binary tree of height 0 consists of a single vertex (called a leaf), and ii. A binary tree of height k +1 consists of a root vertex with exactly two children, at least one of which is a binary tree of height k and the other a binary tree of height at most k (a) (5 points) For the binary tree shown below, give its height, the number of leaves, and the number of internal (non-leaf) vertices (b) (10 points) Prove, by induction, that every binary tree of height h has at most 2h leaves. (c) (10 points) Prove that every binary tree with N leaves has exactly N 1 vertices that are not leavesExplanation / Answer
ANSEWR:
a
Height: 4 (to find the height find the longest path to a leaf node)
numeral of leaf nodes: 5 (nodes with no child)
amount of internal nodes: 4 (nodes with atleast 1 child)
b
Case 1: base case: h = 0
As said, a Binary tree of heigh 0 consist of only one root node,
thus it satisfies the stipulation that a tree of elevation 0 can have at a good number 20 leaf nodes or 1 leaf nodes
Case 2: h = 1
a dual tree of heigh 1 consist of atmost one root node, which consist of 2 child nodes.
thus it satisfies the condition that a tree of height 1 can have at most 21 leaf nodes or 2 leaf nodes
Let us think about that assumption of maximum leaf nodes of a tree with elevation h is 2h
holds true for h = n
so tree of loftiness n can have atmost 2n leafnodes
if we add 2 child joint to each of the leaf nodes we shall have 2n * 2 leafnodes of 2n+1 leafnodes abd height of the tree is increased by 1 i.e. n+1
so if the guess stands true for h = n, it also holds true for h = n+1.
as we know with the intention of the hypothesis hold true for h = 0, it holds true for all h belonginf to entire number