Interview Question

Interview

How do you find duplicates in a binary search tree?

Answer

Interview Answer

3 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
0

can binary search tree have duplicates?

Anonymous on Oct 10, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.