How do I insert into this C++ binary tree?

[davidfaux]

I am trying to write a function that inserts an item into this binary tree in C++.

    template <typename T>
    struct BTree {
      T val;
      BTree<T>* left;
      BTree<T>* right;
      BTree(T v, BTree<T>* l=nullptr, BTree<T>* r=nullptr) :
          val(v), left(l), right(r) {}
    };

Here's my attempt.

    template <typename T>
    void insert(BTree<T>* tree, T item) {
      if (tree == nullptr) {
        tree = new BTree<T>(item);
      } else if (item < tree->val) {
        insert(tree->left, item);
      } else {
        insert(tree->right, item);
      }
    }

I think this function may not be working because I am modifying `tree`, which is a local variable. How do I actually modify the current pointer that `tree` represents, not just `nullptr`?

[Smac89]

The function looks right. If you are worried about modifying the tree in the function, then initialise the tree before doing the insert:

Code I used in a codeforces problem:

class btree {
	btree *left, *right;
	psi info; //#define psi pair< std::string, int >

public:
	btree() : info("", 0){}
	inline string insert (string key) {
		if ( info.first.length() == 0 ){
			info.first = key;
			left = new btree();
			right = new btree();
			return "OK";
		}
		else if ( key == info.first ) {
			info.second = -~info.second;
			return key.append(toString(info.second));
		}
		else if ( key > info.first )
			return right->insert (key);
		else return left->insert (key);
	}
} dataBase;

[cire]

The easiest way is probably to take a reference to a pointer:

    template <typename T>
    void insert(BTree<T>*& tree, T item) {
      if (tree == nullptr) {
        tree = new BTree<T>(item);
      } else if (item < tree->val) {
        insert(tree->left, item);
      } else {
        insert(tree->right, item);
      }
    }