Memory leak in binary tree insertion

[leahloughran]

Hi, I'm working on a binary search tree template and I am getting some memory leakage from the following function. The function is called on the root of the tree and returns the new root with the item inserted into the tree.

I am creating a new node where the item needs to go, which could be what's causing it, however I have a destructor for my tree and it seems to be working in all my other functions. What could be causing this memory leak?

Node* AVLtree::BSTinsert (Node* n, Titem item) //n is the new root of the subtree
  {
    if (n == NULL) //found the right spot to insert
      {
        size++;
        return new Node(item);
      } //make a new node with the item
    else if (n->item == item) //already exists
      return n; //return the unchanged root
    else if (n->item < item)
      n->right = BSTinsert (n->right, item); //insert to the right subtree
    else
      n->left = BSTinsert (n->left, item); //insert to the left subtree
    n = setHeight(n);
    n = balance(n); //balance the tree
    return n;
  }

[kbw]

The new node you create doesn't appear to be in the tree.

The fact is, sometimes you create a new node and sometimes you don't. That's a recipie for disaster.