File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Count Duplicates in BST? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Count Duplicates in BST?" Watch "Count Duplicates in BST?" New topic
Author

Count Duplicates in BST?

William Koch
Ranch Hand

Joined: Sep 26, 2012
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

Joined: Sep 26, 2012
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

Joined: Aug 22, 2010
Posts: 3606
    
  60

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

Joined: Jan 28, 2008
Posts: 5575

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

Joined: Mar 05, 2008
Posts: 2994
    
    9
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

Joined: Sep 26, 2012
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

Joined: Aug 22, 2010
Posts: 3606
    
  60

Neat!

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

Joined: Sep 26, 2012
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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Count Duplicates in BST?
 
Similar Threads
BST problem (Online waiting)
i got a problem, with my test program on binary trees
Matisse designer_problem with displaying drawn circle at JPanel/also animation problem
need help with binary search tree
[Help] Recursive method