Description
1. (15 points) Use a re
ursive tree and the Master theorem to
lassify an algorithm des
ribed by the
following re
urren
e relation: T (n) = 3T (n/2) + n
2 with the initial
ondition T (1) = 1.
(a) master therorem n
2Ωn
log23
therefore T(n) is Θn
2
(b) tree
(
) n
2
(d) n
4
2 n
4
2 n
4
2
(e) n
16
2 n
16
2 n
16
2
(f ) n
2
(1 + 3
16 + ( 3
16 )
2 + …)
(g) cn2
is Θn
2
2. (15 points) Provide a re
ursive algorithm for evaluating an algebrai
expression represented as a binary
tree.
(a) int eval(node n){
(b)
har val=n.val
(
) if ( val=operation)
i. eval(n.left) (do operation) eval(n.right);
ii. else
A. return string2int(val);}
3. (40 points) R-7.16 p. 311
Answer the following questions for both an extended binary tree and a proper binary tree in
(a) and (b), use the Proposition 7.10 to justify your answers.
(a) What is the minimum number of external nodes for both binary trees with height h? Prove your
answer using indu
tion.
i. Minimum for both trees is the
ase when tree is empty. from proposition 7.10
ii. 1 ≤ nE ≤ 2
h
for any tree and h + 1 ≤ nE ≤ 2
h
for proper trees therefore the minimum is
dierent for ea
h
ase
iii. extended tree
ase
iv. initial, indu
tive step p(1) is true p(k)=1;
v. p(k+1)=1;
vi. Proper tree
vii. inital step indu
tive step, p(1) is true p(1)=2, p(k)= k+1
viii. p(k+1)=p(k)+1 //be
ause width of tree in
reases by one
ix. p(k+1)=(k+1)+1
x.
(b) What is the maximum number of external nodes for both binary trees with height h? Prove your
answer using indu
tion.
i. Maximum for both trees is the
ase when tree is full. from proposition 7.10
ii. 1 ≤ nE ≤ 2
h
for any tree and h + 1 ≤ nE ≤ 2
h
for proper trees therefore the maximum is 2
h
iii. indu
tion initial p(1)//one node is true for one proper node Ne=2 for extended Ne=1
iv. indu
tive assumption p(k)=2
k
2
v. proof p(k+1)= 2
k ∗ 2 = 2k+1
(
) Let T be a proper binary tree with height h and n nodes. Prove that
log(n + 1) − 1 ≤ h ≤ (n − 1)/2
i. initial p(h=1,n=(2^h)=2) 1.5 − 1 ≤ h ≤ 2/2 is true
ii. p(k)=log(k
2 + 1) − 1 ≤ k ≤ (k
2
)/2 is true
iii. p(k+1)=log((k + 1)2 + 1) − 1 ≤ (k + 1) ≤ ((k + 1)2
)/2 is also true therefore p(k) is true
Proposition 7.10 (pg 287): Let T be a nonempty binary tree, and let n, nE, nI and h
denote the number of nodes, number of external nodes, number of internal nodes, and height
of T, respe
tively. Then T has the following properties:
1. h + 1 ≤ n ≤ 2
h+1 − 1
2. 1 ≤ nE ≤ 2
h
3. h ≤ nI ≤ 2
h − 1
4. log(n + 1) − 1 ≤ h ≤ n − 1
Also, if T is proper, then it has the following properties:
1. 2h + 1 ≤ n ≤ 2
h+1 − 1
2. h + 1 ≤ nE ≤ 2
h
3. h ≤ nI ≤ 2
h − 1
4. log(n + 1) − 1 ≤ h ≤ (n − 1)/2
4. (15 points) R-7.22 p. 312
Des
ribe, in pseudo-
ode, an algorithm for
omputing the number of des
endents (see the de nition in
the textbook on p. 270) of ea
h node of a binary tree. The algorithm should be based on the Euler
tour traversal.
(a) int num_des
en( Node n){
(b) int num=0;
(
) if (n.left) //left node exist
(d) num=num+num_de
en(n.left) //travese and add left
(e) if (n.right) //right node exist
(f ) num=num+num_de
en(n.right)//traverse and add right
(g) if(!n.left & !n.right) //left and right dont exist
(h) num=num+1
(i) return num;}
5. (15 points) C-7.33 p. 317
Des
ribe, in pseudo-
ode, a nonre
ursive method for performing an inorder traversal of a binary tree
in linear time. (Hint: Use a sta
k.)
(a) traversal(Node n){
(b) sta
k node_sta
k;
(
) while (n!=null){
(d) if (n.left exists){
(e) node_sta
k.push(n); n=n.left; } // left operation area
(f ) else // middle operation
(g) if (n.right exists)
(h) n=n.right; //right operation
(i) else if(n!=null)
(j) n=node_sta
k.pop();
(k) else n=null;
3
