Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to fulfill the following two tasks.

1. Construct a binary search tree(BST).
Initially, the BST is empty. Then given a sequence of distinct integers, you need to insert them into the BST one by one. Lecture notes show more details on insertion.

2. Determine whether the resulted BST after insertion is a balanced BST and return the depth of the BST. A BST is balanced if the depth of the two subtrees of every node never differs by more than 1.


The main function has been provided. You need to complete three functions.

Node* createNode(int data);

Node* insertNode(Node* root, int data);

int getDepth(Node *root);

bool isBalanced(struct Node* root);



Sample Input 1:
5
10 20 30 50 40

Sample Output 1:
Input the number of integers:
Input these integers:
Balanced (Y/N)?
N
The depth of the BST is: 
5

Sample Input 2:
11
2 1 4 10 3 5 7 8 9 6 0

Sample Output 2:
Input the number of integers:
Input these integers:
Balanced (Y/N)?
N
The depth of the BST is: 
7

Sample Input 3:
3
2 1 3

Sample Output 3:
Input the number of integers:
Input these integers:
Balanced (Y/N)?
Y
The depth of the BST is: 
2


Code Template:

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

// Define the structure for BST node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    /*
        Fill in your code here...
    */
}

// Function to insert a node in the BST
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    /*
        Fill in your code here...
    */

    return root;
}

// Function to get the depth of the BST
int getDepth(Node* root) {
    if (root == NULL) {
        return 0;
    }

    /*
        Fill in your code here...
    */
}

// Function to check if the BST is balanced
bool isBalanced(Node* root) {
    if (root == NULL) {
        return true;
    }

    /*
        Fill in your code here...
    */

}

int main()
{
    int n, key;
    Node* root = NULL;
    printf("Input the number of integers:\n");
    scanf("%d",&n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d", &key);
        root = insertNode(root, key);
    }
    
    // Check if the BST is balanced
    printf("Balanced (Y/N)?\n%s\n", isBalanced(root)? "Y":"N");
    printf("The depth of the BST is: \n%d\n", getDepth(root));

    return 0;
}