CareerCup

Traverse the binary tree whichever way you want (preorder, postorder, inorder, level order, etc.). When you visit the node, check if the node exists in the hash set (or hash table), if it does then add it to the list, otherwise add the node to the hash set.

O(n) time and O(n) space

Super cool solution!!!

you dont need to maintain count. instead of hashtable, you could use a set which just has keys.

for each node in tree traversal:
if key is present in set:
insert into list
else:
insert into hash

A sample program in java

package oracle.prakash.investmentbank.test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;


public class AmazonTree<T extends Comparable> {
    public AmazonTree() {
        super();
    }
    public AmazonTree(T data) {
        this.setData(data);
    }
    private AmazonTree<T> left;
    private AmazonTree<T> right;
    private T data;
    private AmazonTree<T> root;
    private ArrayList<AmazonTree<T>> alist = new ArrayList<AmazonTree<T>>();
    
    public static void main(String[] args) {
        AmazonTree<Integer> amazonTree = new AmazonTree<Integer>();
        int[] ints = {10,20,30,40,50,60,60};
        for(int i:ints) {
            amazonTree.insert(i);
        }
        System.out.println(amazonTree.mostDuplicate());
    }
    
    public void insert(T data) {
        AmazonTree<T> root = this.getRoot();
        AmazonTree<T> item = new AmazonTree<T>(data);
        LinkedList<AmazonTree<T>> list = new LinkedList<AmazonTree<T>>();//since in java we have LinkedList which implements queue
        
        if(root==null) {
            this.setRoot(item);
            return;
        }
        list.add(root);
        while(!list.isEmpty()) {
            root = list.poll();
            if(root.getLeft()!=null) list.add(root.getLeft());
            else {
                root.setLeft(item);
                return;
            }
            if(root.getRight()!=null) list.add(root.getRight());
            else {
                root.setRight(item);
                return;
            }
        }
    }
    
    public  ArrayList<AmazonTree<T>> mostDuplicate() 
    {
        
        AmazonTree<T> root = this.getRoot();
        HashSet<T> set = new HashSet<T>();//Set holds unique values
        if(root==null) return  alist;
        LinkedList<AmazonTree<T>> list = new LinkedList<AmazonTree<T>>();
        list.add(root);
        while(!list.isEmpty())
        {
            root = list.poll();
            if(root.getData()!=null) if(!set.add(root.getData())) alist.add(root);
            if(root.getLeft()!=null) list.add(root.getLeft());
            if(root.getRight()!=null) list.add(root.getRight());
        }
        return alist;
    }
    
    

    public void setLeft(AmazonTree<T> left) {
        this.left = left;
    }

    public AmazonTree<T> getLeft() {
        return left;
    }

    public void setRight(AmazonTree<T> right) {
        this.right = right;
    }

    public AmazonTree<T> getRight() {
        return right;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setRoot(AmazonTree<T> root) {
        this.root = root;
    }

    public AmazonTree<T> getRoot() {
        return root;
    }
    
    public String toString() {
        return this.getData()!=null ? this.getData().toString():null;
    }
}

I didn't do anything except posing the interview question. Why my reputation this low?!