William Koch

Ranch Hand

Posts: 76

posted 4 years ago

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.

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

posted 4 years ago

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

posted 4 years ago

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.

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.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 4 years ago

No, that's an artificial limitation. You

- 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

posted 4 years ago

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)

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)

It is sorta covered in the JavaRanch Style Guide. |