COMP352-Assignment 3 Binary Tree Expression Calculator Solved

Question 1
 

A company is involved in shipping large number of containers at a dock. Containers are classified into three categories:  

Category 1: containers need to be accessed by their indices:  lookup, set, add and remove from Category 1. Category 2: containers need to be add and remove before or after certain position including the first and last position of the Category 2.  

Category 3: containers need to be add and remove in a sorted alphabetical order of their destination and any new added container need to follow that order of the Category 3.

 

From the three linear ADTs: List, Positional and Sequence covered in class. discuss which ADT to choose and its underlying implementation for the above containers’ categories.  

 

 

Question 2
 

a)      Draw a single binary tree that gave the following traversals:

  

      Inorder:       C   O   P   Y   R   I   G   H   T   A   B   L   E           Postorder:   C   P   O   R   G   I   T   H   B   A   E   L   Y

 

b)     Assume that the binary tree from part (a) of this question is stored in an array-list as a complete binary tree as discussed in class. Specify the contents of such an array-list for this tree.

 

Question 3 

 

a)     Given a tree T, where n is the number of nodes of T.  

Give an algorithm for computing the depths of all the nodes of a tree T. What is the complexity of your algorithm in terms of Big-O?  

b)     We say that a node in a binary search tree is full if it has both a left and a right child.  

Write an algorithm called Count-Full-Nodes(t) that takes a binary search tree rooted at node t, and returns the number of full nodes in the tree. What is the complexity of your solution?

 

 

Question 4
 

a)      Draw the min-heap that results from the bottom-up heap construction algorithm on the following list of values:

20, 12, 35, 19, 7, 10, 15, 24, 16, 39, 5, 19, 11, 3, 27.

 

Starting from the bottom layer, use the values from left to right as specified above. Show immediate steps and the final tree representing the min-heap. Afterwards perform the operation removeMin 6 times and show the resulting min-heap after each step.

 

b)     Create again a min-heap using the list of values from the above part (a) of this question but this time you have to insert these values step by step using the order from left to right (i.e. insert 20, then insert 12, then 35, etc.) as shown in the above question. Show the tree after each step and the final tree representing the min-heap.

 

 

 

Programming Questions : 

In class, we discussed evaluating arithmetic expressions using a binary tree, this binary tree has leaves that are associated with variables or constants, and whose internal nodes are associated with one of the operators: +,-,* and /.  You can assume parentheses are well-matched, and the only binary operations allowed are +, -, *, and /. In this programming assignment, you will design, using pseudo code, and implementation in Java code, a new version of arithmetic calculators that uses expression trees. Your solution should perform the following:

1.      read valid arithmetic expressions (parentheses are well-matched), where each expression is in a single line. Each arithmetic expression with operands (variables and/or constants) and operators.  

2.      then convert it to an arithmetic expression in a binary tree structure, where each, internal node represents an operator, and its subtrees represent operands. All operators are binary, so every operator has both a left and a right operand. Leaf nodes represent either integers or variables.

3.      use a node in an expression tree. Nodes could be, a leaf node just contains a value (integer or variable); or an internal node has an operator and two Nodes representing its operands.

4.      if the expression contains operand variables, it should prompt the user with those variables to set their values in order to evaluate the expressions.

 

a)      Briefly explain the time and space complexity for the binary tree arithmetic expressions calculator. You can write your explanation in a separate file.

b)     Provide test logs for at least 10 different and sufficiently complex arithmetic expressions that use any of +, -, *, and / operators (including parentheses) in varying combinations, and operand both as variables and constants.