Binary Search Trees V/? - Duplicates

Okie dokie, where was I? Right, duplicates!

Okay so. Possibly the simplest solution is simply to disallow duplicates. If you don't care how many of a given piece of data you have, then you may be willing to simply say, "Oh, we've got this one, no need to add it to the tree."

In that case, we just need to check for equality before checking whether to move right or left, as we were doing before. See below:

function addNode(currentNode, newNode){

    if (currentNode.data == newNode.data){
        return; // if we have a duplicate, we're done!
    } else if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        // code for adding
    } else ( // if our newNode is smaller, move left
        // code for adding
    };

};

There's many a time, however, when you want to keep track of your duplicates. I have seen it suggested that you can pick one side of the tree to allow duplicates on, but not only does this have multiple drawbacks to the runtime of searching through the tree, it goes against the spirit of Binary Search Trees (that being that every node is distinct), so as far as I'm concerned it's not really an option.

A much more elegant solution is to include a count in your nodes. Here is the node class as we have been defining it thus far:

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
} 

We'll add to this a place to keep track of the number of instances of that data piece, like so:

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.count = 1;
        this.left = null; 
        this.right = null; 
    } 
} 

Now if we have a node currentNode we can call currentNode.count to find out how many of that node we have. It should start at one by default, since we'll assume that on creation of a node, you only have the one instance.

So, say we need to add '12' to a tree, but we already have a node of data '12'? We'll create a method on the Node class for increasing its count.

// Node class 
class Node 
{ 
    constructor(data) 
    { 
        this.data = data; 
        this.count = 1;
        this.left = null; 
        this.right = null; 
    } 

    increase(){
        this.count++
    }
} 

So now instead of simply exiting out of our function when we find a duplicate, as we did above, we'll call this increase function.

function addNode(currentNode, newNode){

    if (currentNode.data == newNode.data){
        currentNode.increase(); // increase the count on this node
    } else if (currentNode.data < newNode.data){ // if our newNode is bigger, move right
        // code for adding
    } else ( // if our newNode is smaller, move left
        // code for adding
    };

};

Those are the methods I've come across - if you have a preferred one let me know!