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

// ノード構造体の定義
typedef struct node {
    int val;
    struct node *left;
    struct node *right;
} Node;

// 新しいノードを作成する関数
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// ソート済み配列からバランスの良いBSTを再帰的に構築する関数
Node* buildBalancedBST(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    Node* root = createNode(arr[mid]);
    root->left = buildBalancedBST(arr, start, mid - 1);
    root->right = buildBalancedBST(arr, mid + 1, end);
    return root;
}

// 中間順（In-Order）走査で確認
void inorderTraversal(Node* root) {
    if (!root) return;
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

// メモリ解放
void freeTree(Node* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// メイン関数
int main() {
    int arr[] = {2, 3, 5, 8, 13, 21};  // ソート済みの配列
    int n = sizeof(arr) / sizeof(arr[0]);

    Node* root = buildBalancedBST(arr, 0, n - 1);

    printf("In-Order Traversal: ");
    inorderTraversal(root);  // 昇順で表示されるはず
    printf("\n");

    freeTree(root);  // メモリを解放

    return 0;
}