Try It Now
Site:  Saylor Academy 
Course:  CS202: Discrete Structures 
Book:  Try It Now 
Printed by:  Guest user 
Date:  Friday, July 12, 2024, 11:23 AM 
Description
Work these exercises to see how well you understand this material.
Exercises
 Draw the expression trees for the following expressions:
 a(b + c)
 ab + c
 ab + ac
 bb − 4ac
 ((a_{3}x + a_{2})x + a_{1})x + a_{0}
 Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.

 Draw a binary tree with seven vertices and only one leaf.
 Draw a binary tree with seven vertices and as many leaves as possible.
 Prove that if T is a full binary tree, then the number of leaves of T is one more than the number of internal vertices (nonleaves).
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/adslatex/ads.pdf
This work is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 License.
Solutions
 Answer:
 Answer:
 Answer:
 Answer:
 Solution 1:
Basis: A binary tree consisting of a single vertex, which is a leaf, satisfies the equation leaves = internal vertices + 1
Induction: Assume that for some k ≥ 1, all full binary trees with k or fewer vertices have one more leaf than internal vertices. Now consider any full binary tree with k + 1 vertices. Let T_{A }and T_{B }be the left and right subtrees of the tree which, by the definition of a full binary tree, must both be full. If i_{A }and i_{B }are the numbers of internal vertices in T_{A }and T_{B}, and j_{A }and j_{B }are the numbers of leaves, then j_{A }= i_{A}+ 1 and j_{B }= i_{B}+ 1.
Therefore, in the whole tree, the number of leaves = j_{A }+ j_{B}= (i_{A }+ 1) + (i_{B }+ 1)
= (i_{A }+ i_{B }+ 1) + 1
= (number of internal vertices) + 1  Solution 2:
Imagine building a full binary tree starting with a single vertex. By continuing to add leaves in pairs so that the tree stays full, we can build any full binary tree. Our starting tree satisfies the condition that the number of leaves is one more than the number of internal vertices. By adding a pair of leaves to a full binary tree, an old leaf becomes an internal vertex, increasing the number of internal vertices by one. Although we lose a leaf, the two added leaves create a net increase of one leaf. Therefore, the desired equality is maintained.
 Solution 1: