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