Interview Question

Anonymous Interview

How do you find

duplicates in a binary search tree?
Answer

Interview Answer

2 Answers

0

Do an in-order traversal and keep track of the last item you saw.

Interview Candidate on Oct 13, 2013
0

Do a inorder traversal and store elements in HashMap with frequency update on encountering duplicates

public void duplicateNodes(Node head)
  {
    if(head==null) return;
    if(map.containsKey(head.key))
    {
        map.put(head.key, Integer.parseInt(""+ map.get(head.key) + 1));
    }
    else
        map.put(head.key, 1);
    duplicateNodes(head.left);
    duplicateNodes(head.right);
  }

Map<Integer,Integer> map1 = binarySearchTree.map;
        Iterator it = map1.entrySet().iterator();
        while(it.hasNext())
        {
            Map.Entry pairs = (Map.Entry)it.next();
            if(Integer.parseInt(""+pairs.getValue()) > 1)
                System.out.println("Dup Node " + pairs.getKey());
        }

Nikhil Agarwal on Feb 17, 2014

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up