CS$-303$ Assignment $4$

$(25$ points$)$

$(15$ points$)$ Draw an expression tree corresponding to each of the following:

a$)$ Inorder traversal is: $\frac{x}{y}+3^{**}\frac{b}{c}$

b$)$ Postorder traversal is: $xyz+ab-c*\frac{*}{-}$

c$)$ Preorder traversal is: $*+a-x\frac{y}{c}d$

d$)$ Considered the output of a to$\_$string method below and show the tree that would be built by the following data lines is the binary search tree.

$30$

$15$

$4$

NULL

NULL

$20$

$18$

NULL

$19$

NULL

NULL

NULL

$35$

$32$

NULL

NULL

$38$

NULL

NULL

$(10$ points$)$ Consider the graph above, starting from node $A$ :

a$)$ what is the finish order of the dept first search? $($if two nodes can be reached from a node, give preference to one which is smaller$).$

b$)$ what is the visit sequence of the Breadth first search. $($if two nodes can be reached from a node give preference to one which is alphabetically smaller$).$

Submission guidelines:

For Question $1$ and $2$ provide the text document that has the respective tree and answers to any questions asked, and DFS and BFS traversals of the graph.

$(15$ points$)$ Draw an expression tree corresponding to each of the following:

a$)$ Inorder traversal is: $\frac{x}{y}+3^{**}\frac{b}{c}$

b$)$ Postorder traversal is: $xyz+ab-c*\frac{*}{-}$

c$)$ Preorder traversal is: ${?}^{**}+a-x\frac{y}{c}d$

d$)$ Considered the output of a to$\_$string method below and show the tree that would be built by the following data lines is the binary search tree.

$30$

$15$

$4$

NULL

NULL

$20$

$18$

NULL

$19$

NULL

NULL

NULL

$35$

$32$

NULL

NULL

$38$

NULL

NULL