================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 4: Trees & Binary Search Trees
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Understand tree terminology (root, leaf, height, depth, level)
- Implement Binary Search Tree (BST) operations
- Perform tree traversals (inorder, preorder, postorder, level order)
- Solve tree-based algorithmic problems

================================================================================
PART A: BST BASICS
================================================================================

Structure:
   struct Node {
       int data;
       struct Node *left, *right;
   };

1. Create Node:
   struct Node* createNode(int data);
   Allocate memory, set data, set left and right to NULL.

2. BST Insert:
   struct Node* insert(struct Node *root, int data);
   Insert a value maintaining BST property (left < root < right).
   Test: Insert 50,30,70,20,40,60,80 -> creates a balanced BST.

3. BST Search:
   struct Node* search(struct Node *root, int key);
   Return pointer to node if found, NULL otherwise.
   Test: Search for 40 in above tree -> found

4. Inorder Traversal (Left, Root, Right):
   void inorder(struct Node *root);
   Test: Above tree -> 20 30 40 50 60 70 80

5. Preorder Traversal (Root, Left, Right):
   void preorder(struct Node *root);
   Test: Above tree -> 50 30 20 40 70 60 80

6. Postorder Traversal (Left, Right, Root):
   void postorder(struct Node *root);
   Test: Above tree -> 20 40 30 60 80 70 50

================================================================================
PART B: BST OPERATIONS
================================================================================

7. Find Minimum:
   struct Node* findMin(struct Node *root);
   Go to leftmost node.
   Test: Above tree -> 20

8. Find Maximum:
   struct Node* findMax(struct Node *root);
   Go to rightmost node.
   Test: Above tree -> 80

9. Height of Tree:
   int height(struct Node *root);
   Base case: NULL returns -1 (or 0 depending on convention).
   Test: Above tree -> 2

10. Count Total Nodes:
    int countNodes(struct Node *root);
    Test: Above tree -> 7

11. Count Leaf Nodes:
    int countLeaves(struct Node *root);
    Leaf: both left and right are NULL.
    Test: Above tree -> 4 (nodes 20,40,60,80)

12. Delete Node from BST:
    struct Node* deleteNode(struct Node *root, int key);
    Handle 3 cases: no child, one child, two children.
    For two children: replace with inorder successor (smallest in right subtree).
    Test: Delete 30 from above tree.

================================================================================
PART C: ADVANCED TREE OPERATIONS
================================================================================

13. Level Order Traversal (BFS):
    void levelOrder(struct Node *root);
    Use a queue (array-based). Print level by level.
    Test: Above tree -> 50 30 70 20 40 60 80

14. Print Nodes at Given Level:
    void printLevel(struct Node *root, int level);
    Test: Level 1 of above tree -> 30 70

15. Check if Tree is BST:
    int isBST(struct Node *root);
    Use min/max range approach.
    int isBSTUtil(struct Node *root, int min, int max);

16. Mirror/Invert Tree:
    struct Node* mirror(struct Node *root);
    Swap left and right subtrees recursively.

17. Diameter of Tree:
    int diameter(struct Node *root);
    Longest path between any two nodes (number of edges).

18. Print All Root-to-Leaf Paths:
    void printPaths(struct Node *root, int path[], int pathLen);
    Test: Print all paths from root to each leaf.

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

19. [Easy] Maximum Depth of Binary Tree (LeetCode 104)
    int maxDepth(struct Node *root);
    Test: [3,9,20,null,null,15,7] -> 3

20. [Easy] Symmetric Tree (LeetCode 101)
    Check if tree is a mirror of itself.
    int isSymmetric(struct Node *root);

21. [Easy] Invert Binary Tree (LeetCode 226)
    Invert a binary tree (mirror).
    struct Node* invertTree(struct Node *root);

22. [Medium] Validate Binary Search Tree (LeetCode 98)
    Determine if a binary tree is a valid BST.
    int isValidBST(struct Node *root);

23. [Medium] Lowest Common Ancestor of BST (LeetCode 235)
    Find LCA of two nodes in a BST.
    struct Node* lowestCommonAncestor(struct Node *root, int p, int q);
    Hint: If both p,q < root go left; if both > root go right; else root is LCA.

24. [Easy] Path Sum (LeetCode 112)
    Check if tree has root-to-leaf path with given sum.
    int hasPathSum(struct Node *root, int targetSum);
    Test: [5,4,8,11,null,13,4,7,2,null,null,null,1] target=22 -> true

25. [Medium] Binary Tree Level Order Traversal (LeetCode 102)
    Return level order traversal as arrays per level.

26. [Hard] Serialize and Deserialize BST (LeetCode 449)
    Convert BST to string and reconstruct from string.
    void serialize(struct Node *root, char *str);
    struct Node* deserialize(char *str);

================================================================================