Exercises

  1. Draw the expression trees for the following expressions:
    1. a(b + c)
    2. ab + c
    3. ab + ac
    4. bb − 4ac
    5. ((a3x + a2)x + a1)x + a0


  2. Write out the preorder, inorder, and postorder traversals of the trees in Exercise 1 above.

    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.

  4. 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
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.