Lab Assignment $1$

CS $302$ Advanced Data Structures and File Processing

Problem $1$

Your are given the root nodes of two binary search trees. Determine if both trees store the same numbers.

Note that the trees do not need to be equivalent in structure; the question is only if they store the same numbers.

Implement an iterative and recursive solution.

Problem $2$

Your are given the root node of a binary search tree T and two integers min and max. Note that min and max are

not necessarily stored in the tree. Determine the sum of all keys stored in T that are larger than or equal to min,

and smaller than or equal to max. Implement an iterative and recursive solution.

Implementation

You are given a file Lab$1.$java $($which you can download from canvas$).$ The file contains a class Lab$1$ with the

four functions: problem$1$Iterative, problem$1$Recursive, problem$2$Iterative and problem$2$Recursive.

Implement your solutions in the corresponding functions. You may use the helper functions which are already

implemented in the file given to you. Do not make any changes outside of these four functions $($e$.$

g$.$ by adding helper functions$)$; such changes will be undone. Do not output anything to the terminal.

The program already implemented in the file Lab$1.$java randomly generates test cases. This file contains

a small number of test cases. The seed of the random number generator is set to ensure the same test

cases whenever to program is executed. Note that the purpose of the tests is for you to avoid major mistakes.

Passing all given tests does not imply that your algorithm is correct, especially that is has the expected

runtime.

Submission

For your submission, upload the file Lab$1.$java with your implementation to canvas.

This is an individual assignment. Therefore, a submission is required from each student.

Deadline: On Canvas.