#include <iostream>
#include <vector>
using namespace std;

template <class T>
struct TreeNode {
  T val;
  TreeNode* left;
  TreeNode* right;

  TreeNode(T _val): val(_val) {}
};

template <class T>
class BST {
  TreeNode<T>* root;
  int height;

  BST(TreeNode<T> *r) : root(r) {}

  void insert(const T &val) {
    
  }
  pair<BST<T>*, BST<T>*> splitTree(TreeNode<T>* root, const T &k) {
    if (root == nullptr) return {nullptr, nullptr};
    BST<T>* tlnek, tgnek;
    if (root->val > k) {
      tlnek->insert(root->val);
    }
    if (root->val > k) {
      tgnek->insert(root->val);
    }
    splitTree(root->left, k);
    splitTree(root->right, k);

    return {tlnek, tgnek};
  }
};

int main(int argc, char* argv[]) {
  TreeNode<int> *root; // Need Testing Figures
  Tree<int>* Otree;
  return 0;
}