================================================================================
         DATA STRUCTURES AND ALGORITHMS
         HOMEWORK 7: Binary Search Tree Fundamentals
         State University of Zanzibar (SUZA)
================================================================================

SUBMISSION REQUIREMENTS:
- Submit .c source code file(s) AND handwritten work (scanned/photographed)
- Code must compile and run without errors
- Include your Name, Registration Number, and Date at the top of each file
- VIVA REQUIRED: You must demonstrate and explain your code in person

INTEGRITY DECLARATION:
"I declare that this work is my own. I understand that submitting
AI-generated code or copied work will result in zero marks and
disciplinary action."

Signature: ________________  Date: ________________

================================================================================
PROBLEM 1: BST Construction by Hand (20 marks)
================================================================================

Given the following sequence of insertions:
   45, 25, 65, 15, 35, 55, 75, 10, 20, 30, 40

a) Draw the BST after each insertion step (show all 11 steps).
   [HANDWRITTEN - submit on paper]

b) On your final tree, trace and write out:
   - Inorder traversal
   - Preorder traversal
   - Postorder traversal
   [HANDWRITTEN - show the traversal order step by step]

c) What is the height of the resulting tree?
   Is this tree balanced? Explain why or why not.

================================================================================
PROBLEM 2: BST Insert and Search (30 marks)
================================================================================

Implement a BST with the following functions in C:

   struct Node* createNode(int data);
   struct Node* insert(struct Node *root, int data);
   struct Node* search(struct Node *root, int key);
   void inorder(struct Node *root);
   void preorder(struct Node *root);
   void postorder(struct Node *root);

Requirements:
a) Build the BST from Problem 1's sequence using your insert function
b) Display all three traversals and verify they match your handwritten answers
c) Search for values 35 (should be found) and 42 (should not be found)
d) Count the number of comparisons made during each search

Test Output (verify):
   Inorder:   10 15 20 25 30 35 40 45 55 65 75
   Preorder:  45 25 15 10 20 35 30 40 65 55 75
   Postorder: 10 20 15 30 40 35 25 55 75 65 45

================================================================================
PROBLEM 3: BST Deletion (30 marks)
================================================================================

Using the BST from Problem 2, implement deletion:
   struct Node* deleteNode(struct Node *root, int key);

Handle all three cases with printed explanations:
a) Delete a leaf node: Delete 10
   - Draw tree before and after [HANDWRITTEN]
   - Print inorder traversal after deletion

b) Delete a node with one child: Delete 15
   - Draw tree before and after [HANDWRITTEN]
   - Explain which child takes over

c) Delete a node with two children: Delete 25
   - Draw tree before and after [HANDWRITTEN]
   - Show how you find the inorder successor
   - Explain why you use the inorder successor

d) Write the recursive call trace for deleting 25 [HANDWRITTEN]
   Show each function call and return value.

================================================================================
PROBLEM 4: Height and Leaf Count (20 marks)
================================================================================

Implement:
   int height(struct Node *root);
   int countLeaves(struct Node *root);
   int countNodes(struct Node *root);

a) Show the recursive call trace for height() on your tree [HANDWRITTEN]
   Draw the recursion tree showing each call and return value.

b) Test your functions on the original tree (before any deletions):
   Expected: height=3, leaves=5, total nodes=11

c) Test again after all deletions from Problem 3.
   What are the new values?

================================================================================
VIVA QUESTIONS (be prepared to answer):
================================================================================
1. What is the time complexity of search in a BST? Best case? Worst case?
2. When does a BST degenerate into a linked list?
3. What happens if you insert already-sorted data into a BST?
4. Can you modify your code to find the kth smallest element? (do it live)
5. Explain the difference between inorder successor and inorder predecessor.
6. Why do we use the inorder successor for deletion with two children?

================================================================================
GRADING RUBRIC:
   Problem 1 (Handwritten):     20 marks
   Problem 2 (Code + Output):   30 marks
   Problem 3 (Code + Drawings): 30 marks
   Problem 4 (Code + Trace):    20 marks
   Viva Demonstration:          Required (multiplier: 0 or 1)
   Late Penalty: -10% per day
================================================================================