This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.

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.

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76

posted

0

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 :-(

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.

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.

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

posted

0

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)