CS202: Discrete Structures

1. Draw the expression trees for the following expressions:
   1. a(b + c)
   2. ab + c
   3. ab + ac
   4. bb − 4ac
   5. ((a₃x + a₂)x + a₁)x + a₀
      
      
      
3. Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.
   
   
5. 1. Draw a binary tree with seven vertices and only one leaf.
   2. Draw a binary tree with seven vertices and as many leaves as possible.
      
      
7. 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 (non-leaves).

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.