current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

For the purpose of this problem, the BST is defined to allow duplicates, and the duplicate values will always follow to the right-side of the parent nodes with the same value. For example, with the data:

 1, 2, 2, 2, 2

if the root node has the value 2 (as opposed to 1) then the tree will look like:

          2
         / \
        1   2
             \
              2
               \
                2

The following code scans the tree, identifies any values that are duplicated, and prints the duplicate values, as well as how many times that value is duplicated.

public class DuplicateCountInBST {

    private TreeNode root;

    private class TreeNode {
        TreeNode left;
        int item;
        TreeNode right;

        TreeNode (TreeNode left, int item, TreeNode right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    private class DuplicateInfo {
        int item; 
        int count;

        public DuplicateInfo(int item, int count) {
            this.item = item;
            this.count = count;
        }
    }

    public void print () {
        if (root == null) {
            return;
        }
        // find right most node.
        TreeNode rightMostNode = root;
        while (rightMostNode.right != null) {
            rightMostNode = rightMostNode.right;
        }

        printHelper (root, root.item, new DuplicateInfo(0, 0), rightMostNode);
    }

    // inorder traversal
    // rightmostnode is a guard against skewed trees.
     private void printHelper (TreeNode node, int prevValue, DuplicateInfo duplicateInfo, TreeNode rightMostNode) {
         if (node == null) {
             return;
         }

         printHelper(node.left, node.item, duplicateInfo, rightMostNode);

         if (node.item == duplicateInfo.item) {
             duplicateInfo.item = node.item;
             duplicateInfo.count++;

         } 
         if (node.item != duplicateInfo.item || node == rightMostNode) {
             if (duplicateInfo.count > 1) {
                 System.out.println(duplicateInfo.item + " : " + duplicateInfo.count);
             }
             duplicateInfo.item = node.item;
             duplicateInfo.count = 1;
         }


         printHelper(node.right, node.item, duplicateInfo, rightMostNode);
     }
 }
share|improve this question
add comment

1 Answer

up vote 8 down vote

General

Your code style here is good, the variable names are nice and descriptive, and the algorithm you implement is easy to identify and follow. This is good-looking code. There are a few of nit-picks:

  • the TreeNode class should be a 'static' class ... private static ... because it has no reason to keep a reference to the outer class.
  • Your TreeNode.item should be final even though it is an internal class. final variables make for more apparent logic.
  • this is an opinion thing, but I prefer there to be getter/setter methods even on internal classes. With modern IDE's like Eclipse, IntelliJ and NetBeans, there really is no 'lazy' excuse for it. I prefer methods like node.getRight() instead of node.right
  • your method print() should have a better name like printDuplicates()

Algorithm

The solution you have for this problem appears to work. The algorithm relies on passing a token around, and relies on first walking the right-edge of the tree to create a 'stop-gate'. These two items detract from the solution. There are 'simpler' ways to do this recursive problem without the overheads you have. Consider the functions:

public void printDuplicates() {
    printDuplicatesHelper(root, 0, 0);
}

private void printDuplicatesHelper(final TreeNode node, final int parentval, final int parentcount) {
    if ((node == null || node.item != parentval) && parentcount > 1) {
        System.out.printf("Item %d was duplicated %d times\n", parentval, parentcount);
    }
    if (node == null) {
        return;
    }
    // make sure the parentcount is 0 going left.
    printDuplicatesHelper(node.left, 0, 0);
    printDuplicatesHelper(node.right, node.item, node.item == parentval ? (parentcount + 1) : 1);
}

The above functions also do an in-order scan of the data. The difference is that the recursion is designed to go past the leaf node, and to treat the null node as if it was the end of a duplicate streak. By doing it this way, and by pushing the duplicate-detecting values down with the recursion, you can detect the end-of-duplicates in a much easier pattern.

I created a 'main method' that compares the above code with yours:

 public static void main(String[] args) {
     TreeNode left = new TreeNode(null, 1, new TreeNode(null, 1, null));
     TreeNode right = new TreeNode(
              new TreeNode(null, 5, new TreeNode(null, 5, null)), 6, new TreeNode(null, 6, new TreeNode(null, 6, null)));
    TreeNode top = new TreeNode(left, 3, right);

    DuplicateCountInBST tree = new DuplicateCountInBST();
    tree.root = top;
    tree.print();
    tree.printDuplicates();
}

And the results I get from running the two calls are:

1 : 2
5 : 2
6 : 3
Item 1 was duplicated 2 times
Item 5 was duplicated 2 times
Item 6 was duplicated 3 times
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.