Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Count Duplicates in BST?

William Koch
Ranch Hand
Posts: 76
Can anyone provide a simple algorithm in english or pseudo code for counting the number of duplicate values in a BST? We are assuming that the BST accepts duplicates. Also I can only take in one parameter to the function like such:

function Count_Duplicates(T : Tree_Ptr) return Integer is
begin
return -999;
end Count_Duplicates;

One can perform three actions on a Tree_Ptr like such:
-T.item returns the value inside the root node T
-T.left is the root of the left subtree
-T.right is the root of the right subtree

For example if you view the attached picture the you will see it has 4 duplicates: 1 duplicate A, 2 duplicate B's, and 1 duplicate C.
Capture.JPG

William Koch
Ranch Hand
Posts: 76
I found out another hint if someone can help me. If you do an InOrder Traversal on a Binary search tree the numbers come out in the correct order so we could just count how many occurences of each item and then subtract 1 or something but I do not know how to do that using recursion either. No loops allowed :-(

Martin Vajsar
Sheriff
Posts: 3752
62
If I'm not mistaken, the number of duplicates can be computed as the total number of items minus the number of distinct items. Both of these counts can be computed easily using the inorder traversal.

Edit: I've missed the constraints you've stated in the first post. Don't know how to do that, since you're not allowed to return two numbers from your function, or pass any additional parameter.

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
• 1
tree in your picture is not a BST .

left child must have a key less than it's parent and right child must have a key greater than or equal to it's parent .
so there is no possibility of tree as binary search tree in your picture.

Mike Simmons
Ranch Hand
Posts: 3090
14
• 1
Seetharaman Venkatasamy wrote:left child must have a key less than it's parent and right child must have a key greater than or equal to it's parent .

No, that's an artificial limitation. You can implement a BST with those rules. Or you can allow equal keys on the left but not on the right. Or you can allow equal keys on either side. The last option makes it easier to balance the tree, if that's a goal. Regardless, there's more than one way to code a BST, and the one way that you learned in a particular Algorithms class is not the only way.

William Koch
Ranch Hand
Posts: 76
Solution: Helper Functions are my new favorite thing. I do not know why I didn't think of this before. Search a BST for duplicates! And it is all done using recursion

function Search(X, T) is
# return 1 if X appears in the tree, 0 if it does not
# (normally we would return true/false, but 1/0 is a little more convenient in this application)
if T = null then return 0 # not here
elsif X < T.Item then return Search(T.Left)
elsif X > T.Item then return Search(T.Right)
else return 1 # found X

function Count_Duplicates(T) is
if T = null then return 0
else return Count_Duplicates(T.Left) + Count_Duplicates(T.Right)
+ Search(T.Item, T.Left) + Search(T.Item, T.Right)

Martin Vajsar
Sheriff
Posts: 3752
62
Neat!

I had thought you were limited to one function only. That was where I got stuck...

William Koch
Ranch Hand
Posts: 76
Limited to only passing in one parameter into the main function. There was no rule saying we could not use a helper function.