Description

head
(a)
head (b)
Figure 1
2. [5 points] Consider the binary search tree in Figure 2.
a. What tree results after you insert the nodes 80, 65, 75, 45, 35, and 25, in that order?
b. After inserting the nodes in part a, what tree results when you delete the nodes 50 and 20?
3. [5 points] Draw a (single) binary tree T, such that
• Each internal node of T stores a single character
• A preorder traversal of T yields ALGORITHMS • An inorder traversal of T yields GOLATIHRMS
Programming Part [ 30 points] :
1. Write a java program to count the number of elements in a singly linked list.
– Iteratively
– Recursively
2. Write a java program to evaluate a binary tree containing an expression whichwould use a stack -illustrated in Figure 3.

Figure 2

1
5
– 4 4
2 2 2
X X X 8
+ + + +

Stack to evaluate an expression tree
Figure 3
DO NOT FORGET TO DO A PEER EVALUATION
ENTITY
NO EXTENSIONS
YOU GET A 0 IF YOU DO NOT EVALUATE THE MEMBERS OF YOUR TEAM!
READ/REREAD THE REQUIREMENTS ABOUT FILE TO BE UPLOADED AND ITS NAME}
– Read the README FIRST in the Course Outline section of the course home page in CrsMgr
Do not email your submissions; they will be deleted without opening them!