Balance Binary Search Tree

#include <iostream>
#include <vector>

using namespace std;

class Node {

    public:

    int val;
    Node *left;
    Node *right;

    Node() : val(0), left(nullptr), right(nullptr) { }
    Node(int x) : val(x), left(nullptr), right(nullptr) { }
    Node(int x, Node *left_, Node *right_) : val(x), left(left_), right(right_) { }
};

class Tree {

    public:

    vector<int> vec_inorder;

    Node* Construct (int start, int end) {

        if (start > end) {
            return nullptr;
        }

        int mid = start + (end - start) / 2;
        Node * root = new Node (vec_inorder[mid]);
        root->left = Construct (start, mid - 1);
        root->right = Construct (mid + 1, end);
        return root;
    }

    Node* BalanceBST (Node* root) {
        InOrder (root);
        return Construct (0, vec_inorder.size()-1);
    }

    void InOrder (Node* node) {
        if (node != nullptr) {
            InOrder (node->left);
            vec_inorder.push_back(node->val);
            InOrder (node->right);
        }
    }

    void PreOrder (Node* node) {
        if (node != nullptr) {
            cout << node->val << " ";
            PreOrder (node->left);
            PreOrder (node->right);
        }
    }
};

int main () {
    /* 1
        \
         2
          \
           3
            \
             4 */

    Node node_4(4);
    Node node_3(3, nullptr, &node_4);
    Node node_2(2, nullptr, &node_3);
    Node root_1(1, nullptr, &node_2);

    Tree t;
    Node * balanced_root = t.BalanceBST(&root_1);
    /*     2
          / \
         1   3
              \
               4 */
    cout << "PreOrder traversal of balanced BST : ";
    t.PreOrder(balanced_root);
    return 0;
}

PreOrder traversal of balanced BST : 2 1 3 4