이진 트리를 이진 검색 트리로 변환

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
vector<int> v;

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
  }
}

void storetree(Node* root, int i = 0) {
  if (!root) {
    return;
  }
  storetree(root->left);
  v.push_back(root->data);
  storetree(root->right);
}

void restoretree(Node* root, int& i) {
  if (!root) {
    return;
  }
  restoretree(root->left, i);
  root->data = v[i];
  i++;
  restoretree(root->right, i);
}

void converttoBST(Node* root) {
  if (!root) {
    return;
  }
  storetree(root);
  sort(v.begin(), v.end());
  int i = 0;
  restoretree(root, i);
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  converttoBST(root);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
}