================================================================================
         DATA STRUCTURES AND ALGORITHMS
         HOMEWORK 8: Advanced Tree Operations
         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: Level Order Traversal (25 marks)
================================================================================

Implement level order traversal (BFS) for a BST using a queue.

   void levelOrder(struct Node *root);

Requirements:
a) Use an array-based queue (not linked list) to implement BFS
b) Print nodes level by level with level numbers:
   Level 0: 50
   Level 1: 30 70
   Level 2: 20 40 60 80

c) Also implement:
   void printLevel(struct Node *root, int level);
   int getLevel(struct Node *root, int key);

d) Build tree from: 50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45

Test: What level is node 35 at? What nodes are at level 3?

[HANDWRITTEN] Draw the tree and label each level.

================================================================================
PROBLEM 2: Check if Tree is Balanced (25 marks)
================================================================================

A tree is balanced if for every node, the heights of left and right
subtrees differ by at most 1.

   int isBalanced(struct Node *root);

a) Implement the function. Return 1 if balanced, 0 if not.

b) Test with these trees (build each one):
   Tree A: Insert 50, 30, 70, 20, 40, 60, 80  -> Should be balanced
   Tree B: Insert 10, 20, 30, 40, 50           -> Should NOT be balanced

c) [HANDWRITTEN] For Tree A, show the height calculation at each node.
   Draw the tree with heights labeled at each node.

d) What is the time complexity of your isBalanced function?
   Can you make it O(n)? (Hint: calculate height and check balance
   in the same recursion)

================================================================================
PROBLEM 3: Lowest Common Ancestor (25 marks)
================================================================================

Find the lowest common ancestor (LCA) of two nodes in a BST.

   struct Node* LCA(struct Node *root, int p, int q);

Algorithm for BST:
- If both p and q are less than root, LCA is in left subtree
- If both p and q are greater than root, LCA is in right subtree
- Otherwise, root is the LCA

a) Implement the function.

b) Test with tree: 50, 30, 70, 20, 40, 60, 80
   - LCA(20, 40) = ? (expected: 30)
   - LCA(20, 60) = ? (expected: 50)
   - LCA(60, 80) = ? (expected: 70)
   - LCA(20, 30) = ? (expected: 30)

c) [HANDWRITTEN] For each test case above, trace the path from root
   to the LCA. Show which comparisons are made at each step.

d) What is the time complexity? How does it relate to tree height?

================================================================================
PROBLEM 4: Sorted Array to Balanced BST (25 marks)
================================================================================

Given a sorted array, construct a height-balanced BST.

   struct Node* sortedArrayToBST(int arr[], int start, int end);

Algorithm:
- Find middle element -> make it root
- Recursively build left subtree from left half
- Recursively build right subtree from right half

a) Implement the function.

b) Test with: int arr[] = {1, 2, 3, 4, 5, 6, 7};
   Expected tree (one valid answer):
        4
       / \
      2   6
     / \ / \
    1  3 5  7

c) Verify the tree is balanced using your isBalanced function from Problem 2.
d) Print inorder traversal (should give back the original sorted array).

e) [HANDWRITTEN] Draw the recursion tree for the function call with array
   {1, 2, 3, 4, 5, 6, 7}. Show each recursive call with its start and
   end indices.

================================================================================
VIVA QUESTIONS (be prepared to answer):
================================================================================
1. What is the difference between BFS and DFS? Which traversals are DFS?
2. Why is a balanced tree important? What is the height of balanced vs skewed?
3. Can you find LCA in a general binary tree (not BST)? How would it differ?
4. If the sorted array has 1000 elements, what is the height of the resulting BST?
5. Modify your level order to print in zigzag order (left-to-right, then right-to-left).
6. What is an AVL tree? How does it maintain balance?

================================================================================
GRADING RUBRIC:
   Problem 1 (Level Order):      25 marks
   Problem 2 (Balanced Check):   25 marks
   Problem 3 (LCA):              25 marks
   Problem 4 (Array to BST):     25 marks
   Viva Demonstration:           Required (multiplier: 0 or 1)
   Late Penalty: -10% per day
================================================================================