Dilemma of Const type in C++

Question

I'm trying to implement BST in c++ using recursion. However, I found myself in dilemma.

In the Insert function, I use reference TreeNode *&nodeto pass the function argument. I don't want make the reference const, because I need change node in Insert function. On the other side, when I call function like tree.Insert(10, tree.Getroot()), it occurs error because function Getroot creates temporary variable which can't not be assigned to non-const reference. And I know I can easily fix it by making the TreeNode *rootpublic, but I don't want do that.

What should I do to fix it or is there any better design? Please help, thanks in advance. Here's the head file.

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

class TreeNode
{
public:
  TreeNode(int x = 0,TreeNode* l = nullptr, TreeNode* r = nullptr)
  : element(x), left(l), right(r) { }

  int element;
  TreeNode* left;
  TreeNode* right;
};


class BST
{
public:
  BST(TreeNode *t = nullptr) : root(t) {}

  void Insert(int x, TreeNode*& node)
  {
    if (node == nullptr) {
      node = new TreeNode(x, nullptr, nullptr);
      if (node == nullptr)
        std::cout << "Insert Failure" << std::endl;
    }
    else if (node->element < x) {
      Insert(x, node->right); //easy to make a mistake
    }
    else if (node->element > x) {
      Insert(x, node->left);
    }
  }

  TreeNode *Getroot()
  {
    return root;
  }

private:
  TreeNode* root;
};

#endif

Answer 1

Implement Insert at a node level as well as tree level. Then the insert logic should either be handled at the root level by the tree or at depth by the node you're inserting at. I have an example tree implemented here. It might not be the best implementation but maybe it will be useful to you.

Answer 2

#ifndef __BINARYTREENODE__
#define __BINARYTREENODE__

class BinaryTreeNode {

public:
    BinaryTreeNode(int);
    int element;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

#endif /* __BINARYTREENODE__ */


    #ifndef __BINARYSEARCHTREE__
    #define __BINARYSEARCHTREE__

    #include "BinaryTreeNode.h"

    using namespace std;

    class BinarySearchTree {

    public:
        BinarySearchTree();
        ~BinarySearchTree();
        void insert(int);

    private:
        BinaryTreeNode *root;
        void insert(int, BinaryTreeNode * & n);

    };

    #endif /* __BINARYSEARCHTREE__ */


#include "BinarySearchTree.h"
#include <iostream>
using namespace std;

BinarySearchTree::BinarySearchTree(){}

void BinarySearchTree::insert(int element)
{
    insert(element, this->root);
}
void BinarySearchTree::insert(int element, BinaryTreeNode* & n)
{
    if (n == 0)
    {
        n = new BinaryTreeNode(element);
    }
    else if (n->element > element)
    {
        insert(element, n->left);
    }
    else if (n->element < element)
    {
        insert(element, n->right);
    }
}