fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. class TreeNode {
  7. public:
  8.     int value;
  9.     TreeNode* left;
  10.     TreeNode* right;
  11.  
  12.     TreeNode(int val) {
  13.         value = val;
  14.         left = right = nullptr;
  15.     }
  16. };
  17.  
  18. // Function to build a balanced BST from a sorted array
  19. TreeNode* buildBalancedBST(vector<int>& arr, int start, int end) {
  20.     // Base case: if start > end, return nullptr (no nodes left to insert)
  21.     if (start > end) {
  22.         return nullptr;
  23.     }
  24.  
  25.     // Find the middle element and make it the root
  26.     int mid = (start + end) / 2;
  27.     TreeNode* root = new TreeNode(arr[mid]);
  28.  
  29.     // Recursively build the left and right subtrees
  30.     root->left = buildBalancedBST(arr, start, mid - 1);  // Left subtree
  31.     root->right = buildBalancedBST(arr, mid + 1, end);   // Right subtree
  32.  
  33.     return root;
  34. }
  35.  
  36. // In-order traversal to print the tree
  37. void inorderTraversal(TreeNode* root) {
  38.     if (root != nullptr) {
  39.         inorderTraversal(root->left);
  40.         cout << root->value << " ";
  41.         inorderTraversal(root->right);
  42.     }
  43. }
  44.  
  45. int main() {
  46.     vector<int> values = {10, 5, 15, 3, 7, 20};  // Input array
  47.  
  48.     // Sort the array first to ensure balanced tree
  49.     sort(values.begin(), values.end());
  50.  
  51.     // Build the balanced BST
  52.     TreeNode* root = buildBalancedBST(values, 0, values.size() - 1);
  53.  
  54.     // Print the in-order traversal of the tree (should be sorted)
  55.     inorderTraversal(root);
  56.     cout << endl;
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
10 5 15 3 7 20
stdout
copy 
3 5 7 10 15 20
https://ideone.com/WMAd05
Building a Balanced Binary Search Tree:
To construct a balanced binary search tree, one common approach is:
- Sort the elements.
- Build the tree from the sorted array by picking the middle element as the root, and recursively applying the
same process to the left and right halves of the array.
language:
C++ (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!