Consider the set T of binary trees that have the following property: Consider th
ID: 3771729 • Letter: C
Question
Consider the set T of binary trees that have the following property:
Consider the set T of binary trees that have the following property: for each node in the tree, the heights of that node's left, and right subtrees differ by at most 1. Give a recursive definition for the set T. Prove the following property of the trees in T: for a tree t of height n, t has at least (1.5)^n -1 nodes. You may choose to use your recursive definition of T in your proof (if you do not use your recursive definition, then complete induction will be required).Explanation / Answer
a) The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.
b)
Firstly I am not sure about (1.5)^n -1. As per my knowledge it would be 2^(n+1) - 1.
Here theorem:
--------------
i) number of leafes in T is atleast n+1 and at most 2^n.
ii) number of internal modes in T is atleast n and at most 2^n - 1
iii) number of nodes in T is atleast 2n+2 and at most 2^(n+1) - 1.
iv) log(n+1) -1<=h<=(n-1)/2