Assuming there are no duplicate data elements, the shape of a binary tree can be uniquely determined given the inorder traversal order alongside either the preorder or postorder traversal order. In this lab, you will implement a recursive procedure for reconstruc ng a binary tree (of characters) given the pre- and inorder traversal orders (as strings).
First, your TA will review trees, recursive procedures over trees, and the traversal orders.
Exercise
• er the TA’s lesson, complete the following steps:
1. Download the provided code and read it over. The RebuildBinaryTree class contains a stub for the rebuildTree method that you will implement.
2. First, determine the root node using the preorder traversal.
3. Next, use your knowledge of the root node to determine the por ons of the
traversals that represent the le subtree and right subtree. Consider the substring method and the indexOf method for the string manipula ons.
4. Recurse on the le and right subtree traversals.
5. To complete the recursive case, recombine the returned rebuilt trees to reconstruct the tree overall.
6. Finally, determine an appropriate base case. Implement your base case to complete the rebuildTree method.
7. Test your code with the example from lecture, as well as a few other examples, to ensure your code works as expected.
Conclusion
In this lab, you implemented a method for reconstruc ng a binary tree given its preorder and inorder traversals. More importantly, you prac ced wri ng complex recursive procedures over recursively-defined data structures.
