Keep track of duplicates in BST

Question

A similar question was asked here on SO: [BST with duplicates

User Sazzadur Rahaman posted the three scenarios for accomplishing BST with duplicates, but I need to know how to implement the third situation he mentioned which looks something like this:

Assume we are using the input: "RABSAB."

The tree with the counter variable in brackets would look like this:

    R(1)
   /  \
  /    \
 A(2)  S(1)
  \
   \
   B(2)

So basically, I want each element(node) to have a specific counter variable.

Is what I'm trying to do possible to implement in just my insert method? Or would I need some sort of other method in my BSTTree/Node class?

****EDIT** my BSTNode class, made changes from Compass's recommendations.

public class BSTNode {
    String key;
    BSTNode left, right;
    int count=1;

    public BSTNode(String key) {
        this.key = key;
    }

    public void insert(String x) {
        if (x.compareTo(this.key) > 0) {
            if (right != null) {
                right.insert(x);
            } else {
                right = new BSTNode(x);
            }
        } //Go right

        else if (x.compareTo(this.key) < 0) {
            if (left != null) {
                left.insert(x);
            } else {
                left = new BSTNode(x);
            }
        } //Go left

        else if (x.compareTo(this.key) == 0) {
            count++;
        } // It's a duplicate, update the count
    }
}

EDIT, updated my output incrementing a counter like that doesn't seem to give the correct output, I'm inserting "RABSAB" and trying to count the number of duplicate nodes.

Inserting as follows:

String line = "R A B S A B";
String[] words = line.split(" ");

    for (int i = 0; i < words.length; i++) {
        t1 = t1.Insert(words[i], t1);
        System.out.println(words[i] + " : " + t1.count);
    }

I get the following output:

R : 1
A : 1
B : 1
S : 1
A : 1
B : 1

Thanks for your time everyone.

What does your BSTNode class look like? This might be the place where you might have a counter to increment. — Justin, Sep 24 '14 at 17:23

Compass · Accepted Answer · 2014-09-24T20:37:20.237

0

Inside your BSTNode class, outside of the Insert method, declare int counter = 1;

Then, within your else, you would do counter++;

So on creating a node, you'd have 1 of the element (since you created it, you know it exists).

As additional keys that match are found, you would increment the counter.

I do feel like there is an implementation issue with your Insert method (which should be lower-case insert to follow conventions). You're passing a Node t which I assume is the child of the Node. That should probably be declared as a field just like counter is.

Sample Pseudocoded Integer-based Node with Duplicates

public class Node() {
    int value; //node's value
    int counter = 1; //how many items of same type at node
    Node leftChild = null;
    Node rightChild = null;

    public Node(int value) {
        this.value = value;
    }


    public void insert(int newValue) {
        if(newValue > value) {
            if(rightChild != null)
                rightChild.insert(newValue); //we tell the child to deal with it
            else
                rightChild = new Node(newValue); //we make it a child
        }
        else if(newValue < value) {
            if(leftChild != null)
                leftChild.insert(newValue);
            else
                leftChild = new Node(newValue);
        }
        else if(newValue == value) {
            counter++; // we found a duplicate, increase count
        }
    }
}

edited Sep 24 '14 at 20:37

answered Sep 24 '14 at 17:23

Compass

5,867
4
30
42

Thanks for the reply. I added a global counter variable within my BSTNode class and incrementing in the else statement, but stil doesn't achieve my desired output. I do feel like I'm either not testing right or am missing something (perhaps checks for the parent nodes?).. – Sep 24 '14 at 20:15
@Lameste it should not be a global variable. I will write some pseudocode in the answer so you can see the basic idea. – Compass Sep 24 '14 at 20:32
@Lameste I've updated my answer with an integer-based Node with insert. If you understand how this works, you should be able to see how it will work with your chars. – Compass Sep 24 '14 at 20:38
Ive implemented it but it unfortunately gives me the same output. – Sep 24 '14 at 21:52
@Lameste Consider the differences between my insert and your insert. Node inserts normally should only consider the element to be inserted, and not any additional variables. You don't need to pass a node to the insert to make it work, and that is very likely what is causing the problem, as t1 is not your head node after the first insert operation. – Compass Sep 24 '14 at 21:55
I've edited my post to include my BSTNode class code and implementation based on your recommendations. Still unfortunately getting the same output. – Sep 24 '14 at 22:20
I fixed it by chaning count to static int instead, since the recursive call kept changing my variable. Thanks so much for your time! – Sep 24 '14 at 22:46

score 0 · Answer 2 · edited Sep 24 '14 at 18:15

0

This will work.

 else {
          t.count++;
      } 
 return t;

edited Sep 24 '14 at 18:15

R.daneel.olivaw

2,681
21
31

answered Sep 24 '14 at 17:24

SJha

1,510
1
10
17

Please take a look at my edit. I've tried this but the recursion always resets the counter. – Sep 24 '14 at 20:08

Keep track of duplicates in BST

2 Answers2