Assignment: Exploring Recursion and Trees in Java

Objective

The goal of this assignment is to explore the concepts of recursion and trees in Java, understand how they work together, and demonstrate their applications with simple code examples. This assignment will enhance your understanding of how these two concepts complement each other and prepare you for solving real-world problems involving hierarchical data.

Assignment Description

You will work in groups (no more than 4 members) to research and explain the following:

1. What is Recursion?
   • Define recursion and its role in problem-solving.
   • Explain the components of recursion: base case and recursive case.
2. What is a Tree in Java?
   • Define trees and their structure.
   • Explain the different types of trees (binary trees, binary search trees, etc.).
3. How Do Recursion and Trees Work Together?
   • Explain why recursion is a natural choice for working with trees. *Provide examples of common operations on trees (e.g., traversals, height calculation).
4. Use Cases for Recursion and Trees
   • Identify at least three real-world scenarios where recursion and trees are applied (e.g., decision trees, parsing expressions, or file systems).

Submission Requirements

1. Research Paper
   • A concise 3-5 page document summarizing your findings.
   • Include clear definitions, examples, and use cases.
   • Discuss how recursion simplifies operations on trees and its limitations.
2. Code Examples
   • Each group member must contribute two code examples (e.g., tree traversal, height calculation, or any proof-of-concept operation combining recursion and trees).
   • At least one example per group must include:
   • A recursive operation.
   • A tree structure implemented in Java.
   • Provide inline comments to explain the code logic.
3. Repository Submission
   • Create a Git repository for your group (assigned in class).
   • Organize the repository with the following structure:

/research_paper/ (PDF file of your research)
/code_examples/
member1_example1.java
member1_example2.java
member2_example1.java
...

Grading Criteria

Criteria Points

• Research Paper Content 30
• Clear and Accurate Definitions 10
• Real-World Use Cases 10
• Code Examples 40
• Correctness of Code 20
• Code Readability and
• Comments 10
• Organization of Repository 10
• Total 100

Code Example Ideas

To help guide you, here are some ideas for code examples:

1. Tree Traversals: Write recursive methods for preorder, inorder, or postorder traversals.
2. Tree Height Calculation: Write a recursive function to calculate the height of a tree.
3. Sum of Nodes: Implement a method to calculate the sum of all node values in a tree.
4. Searching in a Binary Search Tree: Demonstrate recursive search in a BST.
5. Constructing a Tree: Write a recursive method to build a tree from an array.

Rules

• Group size: Max 4 members.
• Each group member must contribute their own 2 code examples.
• Collaborate effectively and divide tasks to ensure even contribution.