/*
 * TREE EXERCISES
 * Complete the functions as described in each exercise.
 * Test your solutions using the main() function provided.
 */

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// BST Node structure
struct Node {
    int data;
    struct Node *left, *right;
};

// Provided: Create a new node
struct Node* createNode(int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Provided: Insert into BST
struct Node* insert(struct Node *root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

// Provided: Build a sample BST for testing
// Inserts: 50, 30, 70, 20, 40, 60, 80
struct Node* buildSampleTree() {
    struct Node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);
    return root;
}

/* ============================================================
 * EXERCISE 1: Count Total Nodes
 * Parameters: root - pointer to root of BST
 * Returns: total number of nodes in the tree
 * Example: Tree with 50,30,70,20,40,60,80 -> 7
 * ============================================================ */
int countNodes(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 2: Count Leaf Nodes
 * A leaf node has no children (both left and right are NULL)
 * Parameters: root - pointer to root of BST
 * Returns: number of leaf nodes
 * Example: Tree with 50,30,70,20,40,60,80 -> 4 (20,40,60,80)
 * ============================================================ */
int countLeaves(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 3: Find Height of BST
 * Height = number of edges on longest path from root to leaf
 * Parameters: root - pointer to root of BST
 * Returns: height of tree (-1 for empty tree)
 * Example: Tree with 50,30,70,20,40,60,80 -> 2
 * ============================================================ */
int height(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 4: Find Minimum Value
 * In a BST, minimum is the leftmost node
 * Parameters: root - pointer to root of BST
 * Returns: minimum value in the tree
 * Example: Tree with 50,30,70,20,40,60,80 -> 20
 * ============================================================ */
int findMin(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 5: Find Maximum Value
 * In a BST, maximum is the rightmost node
 * Parameters: root - pointer to root of BST
 * Returns: maximum value in the tree
 * Example: Tree with 50,30,70,20,40,60,80 -> 80
 * ============================================================ */
int findMax(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 6: Search for a Value
 * Parameters: root - pointer to root, key - value to search
 * Returns: 1 if found, 0 if not found
 * Example: Search 40 in above tree -> 1 (found)
 *          Search 45 in above tree -> 0 (not found)
 * ============================================================ */
int searchBST(struct Node *root, int key) {
    // Your code here
}

/* ============================================================
 * EXERCISE 7: Inorder Traversal
 * Print nodes in order: Left, Root, Right
 * Parameters: root - pointer to root of BST
 * Returns: void (prints values)
 * Example: Tree with 50,30,70,20,40,60,80 -> 20 30 40 50 60 70 80
 * ============================================================ */
void inorder(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 8: Check if Tree is Valid BST
 * A valid BST: all left subtree values < root < all right subtree values
 * Parameters: root - pointer to root
 * Returns: 1 if valid BST, 0 otherwise
 * Hint: Use helper function with min/max range
 *       int isBSTUtil(struct Node *root, int min, int max);
 * ============================================================ */
int isBSTUtil(struct Node *root, int min, int max) {
    // Your code here
}

int isBST(struct Node *root) {
    return isBSTUtil(root, -99999, 99999);
}

/* ============================================================
 * EXERCISE 9: Find Level of a Node
 * Root is at level 0
 * Parameters: root - pointer to root, key - value to find
 * Returns: level of the node, -1 if not found
 * Example: Level of 40 in above tree -> 2
 *          Level of 50 -> 0 (root)
 * ============================================================ */
int findLevel(struct Node *root, int key) {
    // Your code here
}

/* ============================================================
 * EXERCISE 10: Count Nodes at a Given Level
 * Parameters: root - pointer to root, level - target level
 * Returns: number of nodes at that level
 * Example: Level 1 of above tree -> 2 (nodes 30, 70)
 *          Level 2 -> 4 (nodes 20, 40, 60, 80)
 * ============================================================ */
int countAtLevel(struct Node *root, int level) {
    // Your code here
}

/* ============================================================
 * EXERCISE 11: Sum of All Nodes
 * Parameters: root - pointer to root of BST
 * Returns: sum of all node values
 * Example: 50+30+70+20+40+60+80 = 350
 * ============================================================ */
int sumNodes(struct Node *root) {
    // Your code here
}

/* ============================================================
 * EXERCISE 12: Check if Two Trees are Identical
 * Two trees are identical if they have same structure and values
 * Parameters: root1, root2 - pointers to roots of two trees
 * Returns: 1 if identical, 0 otherwise
 * ============================================================ */
int isIdentical(struct Node *root1, struct Node *root2) {
    // Your code here
}

/* ============================================================
 * EXERCISE 13: Lowest Common Ancestor in BST
 * Find the lowest common ancestor of two nodes in a BST
 * Parameters: root, p, q - root pointer and two values
 * Returns: pointer to LCA node
 * Example: LCA of 20 and 40 -> 30
 *          LCA of 20 and 60 -> 50
 * Hint: If both values < root, go left.
 *       If both values > root, go right.
 *       Otherwise, root is the LCA.
 * ============================================================ */
struct Node* lowestCommonAncestor(struct Node *root, int p, int q) {
    // Your code here
}


/* ============================================================
 * MAIN FUNCTION - Tests all exercises
 * ============================================================ */
int main() {
    struct Node *root = buildSampleTree();
    // Tree:        50
    //            /    \
    //          30      70
    //         /  \    /  \
    //        20  40  60  80

    printf("=== Exercise 1: Count Nodes ===\n");
    printf("Total nodes: %d (expected: 7)\n\n", countNodes(root));

    printf("=== Exercise 2: Count Leaves ===\n");
    printf("Leaf nodes: %d (expected: 4)\n\n", countLeaves(root));

    printf("=== Exercise 3: Height ===\n");
    printf("Height: %d (expected: 2)\n\n", height(root));

    printf("=== Exercise 4: Find Minimum ===\n");
    printf("Minimum: %d (expected: 20)\n\n", findMin(root));

    printf("=== Exercise 5: Find Maximum ===\n");
    printf("Maximum: %d (expected: 80)\n\n", findMax(root));

    printf("=== Exercise 6: Search ===\n");
    printf("Search 40: %d (expected: 1)\n", searchBST(root, 40));
    printf("Search 45: %d (expected: 0)\n\n", searchBST(root, 45));

    printf("=== Exercise 7: Inorder Traversal ===\n");
    printf("Inorder: ");
    inorder(root);
    printf("\n(expected: 20 30 40 50 60 70 80)\n\n");

    printf("=== Exercise 8: Is BST? ===\n");
    printf("Is BST: %d (expected: 1)\n\n", isBST(root));

    printf("=== Exercise 9: Find Level ===\n");
    printf("Level of 40: %d (expected: 2)\n", findLevel(root, 40));
    printf("Level of 50: %d (expected: 0)\n\n", findLevel(root, 50));

    printf("=== Exercise 10: Count at Level ===\n");
    printf("Nodes at level 1: %d (expected: 2)\n", countAtLevel(root, 1));
    printf("Nodes at level 2: %d (expected: 4)\n\n", countAtLevel(root, 2));

    printf("=== Exercise 11: Sum of Nodes ===\n");
    printf("Sum: %d (expected: 350)\n\n", sumNodes(root));

    printf("=== Exercise 12: Identical Trees ===\n");
    struct Node *root2 = buildSampleTree();
    printf("Same trees: %d (expected: 1)\n", isIdentical(root, root2));
    root2 = insert(root2, 99);
    printf("Different trees: %d (expected: 0)\n\n", isIdentical(root, root2));

    printf("=== Exercise 13: LCA ===\n");
    struct Node *lca = lowestCommonAncestor(root, 20, 40);
    if (lca) printf("LCA(20,40): %d (expected: 30)\n", lca->data);
    lca = lowestCommonAncestor(root, 20, 60);
    if (lca) printf("LCA(20,60): %d (expected: 50)\n", lca->data);

    return 0;
}