Create a Balanced bst
Thu Nov 16 2023 03:28:33 GMT+0000 (Coordinated Universal Time)
Saved by @Astik
#include <stdio.h> #include <stdlib.h> // Define a structure for a binary tree node struct Node { int data; struct Node* left; struct Node* right; }; // Function to create a new node struct Node* newNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // Function to perform an inorder traversal and store elements in the array void storeInorder(struct Node* root, int* arr, int* index) { if (root == NULL) return; storeInorder(root->left, arr, index); arr[(*index)++] = root->data; storeInorder(root->right, arr, index); } // Function to create a balanced BST from a sorted array struct Node* sortedArrayToBST(int arr[], int start, int end) { if (start > end) return NULL; int mid = (start + end) / 2; struct Node* root = newNode(arr[mid]); root->left = sortedArrayToBST(arr, start, mid - 1); root->right = sortedArrayToBST(arr, mid + 1, end); return root; } // Function to convert a normal BST to a balanced BST struct Node* convertToBalancedBST(struct Node* root) { int n = 0; int index = 0; storeInorder(root, NULL, &n); int* arr = (int*)malloc(n * sizeof(int)); storeInorder(root, arr, &index); struct Node* newRoot = sortedArrayToBST(arr, 0, n - 1); free(arr); return newRoot; } // Function to insert a node into a BST struct Node* insert(struct Node* root, int data) { if (root == NULL) return newNode(data); if (data < root->data) root->left = insert(root->left, data); else if (data > root->data) root->right = insert(root->right, data); return root; } // Function to take input from the user and build a BST struct Node* buildBST() { struct Node* root = NULL; int n, data; printf("Enter the number of elements in the BST: "); scanf("%d", &n); printf("Enter the elements of the BST: "); for (int i = 0; i < n; i++) { scanf("%d", &data); root = insert(root, data); } return root; } // Function to perform an inorder traversal and print the tree void inorderTraversal(struct Node* root) { if (root == NULL) return; inorderTraversal(root->left); printf("%d ", root->data); inorderTraversal(root->right); } // Function to free memory in the tree void freeTree(struct Node* root) { if (root == NULL) return; freeTree(root->left); freeTree(root->right); free(root); } int main() { struct Node* root = buildBST(); printf("Original BST in inorder traversal: "); inorderTraversal(root); printf("\n"); struct Node* balancedRoot = convertToBalancedBST(root); printf("Balanced BST in inorder traversal: "); inorderTraversal(balancedRoot); printf("\n"); freeTree(root); freeTree(balancedRoot); return 0; }
Comments