Description
Consider a binary search tree that is generated by inserting the following integers in the given sequence:
The traversals of the above tree is as follows:
– in-order: 15, 20, 25, 30, 32, 35, 40, 45, 55, 60, 65, 75, 95
– pre-order: 35, 25, 15, 20, 30, 32, 65, 45, 40, 55, 60, 95, 75
– post-order: 20, 15, 32, 30, 25, 40, 60, 55, 45, 75, 95, 65, 35
If this binary search tree (BST) were to be saved to a file, we could consider any of the above traversals to save the
BST, but to reconstruct the BST to maintain initial structure, we either need to save it in pre-order or post-order.
The algorithm to reconstruct a BST with a given pre-order traversal is as follows:
1. the first element in the current input array is the root.
2. loop from the second element until the end.
3. stop when the element is greater than the root.
4. split the array into two sub-arrays, implying the elements in the left and right subtrees.
5. recursively start from step one to reconstruct the left and right subtrees from the two sub-arrays.
**Example**
Pre-Order traversal input: 35, 25, 15, 20, 30, 32, 65, 45, 40, 55, 60, 95, 75
Root: 35
Left-sub-array: 25, 15, 20, 30, 32
Right-sub-array: 65, 45, 40, 55, 60, 95, 75
Recursively repeat for left and right sub-arrays.
The opposite logic can be applied to a post-order traversal, the algorithm of which is as follows:
1. the last element `N` in the current input array is the root.
2. loop from beginning to `N-1`.
3. stop when the element is greater than the root.
4. split the array into two sub-arrays, implying the elements in the left and right subtrees.
5. recursively start from step 1 to reconstruct the left and right subtrees from the two sub-arrays.
**Example**
Post-Order traversal input: 20, 15, 32, 30, 25, 40, 60, 55, 45, 75, 95, 65, 35
Root: 35
Left-sub-array: 20, 15, 32, 30, 25
Right-sub-array: 40, 60, 55, 45, 75, 95, 65
Recursively repeat for left and right sub-arrays.
## Assignment Guidelines
There are a number of goals of this assignment:
1. implement the following methods in the `BST` class (available on Canvas):
– `isEqualTo(BST<?> otherTree)` – should be called to check if a BST is equal to another BST and return a boolean
value.
– `isEqualTo(TreeNode<?> root1, TreeNode<?> root2)` – private helper method to implement the recursive checking of
the two BSTs. Recursively check both the trees by traversing both the trees at the same time. Traversal type is
flexible as long as all nodes are visited. Return true if recursion is complete or false if any elements mismatch
during traversal.
2. implement the following methods in the `BSTReconstructor` class (available on Canvas):
– `preOrderReconstructor(List<Integer> inputArray)` – receives an input array of pre-order traversal items, creates
the original BST, and saves the reconstructed tree in the `preOrderReconstructedBST` variable.
– `postOrderReconstructor(List<Integer> inputArray)` – receives an input array of post-order traversal items,
creates the original BST, and saves the reconstructed tree in the `postOrderReconstructedBST` variable.
This code should all be tested and validated with the `main()` method in the `BSTReconstructor` class.
## Submission
Submit the `BST` and `BSTReconstructor` classes on Canvas.
