## Amazon Interview Question

SDE-2s**Country:**United States

public static int maxDistinct(Tree root){

Set<String> uniq = new HashSet<>();

if(root == null){

return 0;

}

return getMax(root, uniq);

}

private static int getMax(Tree root, Set uniq){

if(root == null){

return uniq.size();

}

int l = 0;

int r = 0;

if(uniq.add(root.data)){

l = getMax(root.left, uniq);

r = getMax(root.right, uniq);

uniq.remove(uniq.size()-1);

}

return Math.max(l,r);

}

```
public static int getDisCnt(Tree root){
Set<String> uniq = new HashSet<>();
if(root == null){
return 0;
}
return getMaxHelper(root, uniq);
}
private static int getMaxHelper(Tree root, Set<String> uniq){
if(root == null){
return uniq.size();
}
int l = 0;
int r = 0;
if(uniq.add(root.data)){
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
uniq.remove(uniq.size()-1);
}
else{
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
}
return Math.max(l, r);
```

}

Use a hashset to keep track of unique nodes. While traversing the tree.

```
public static int getDisCnt(Tree root){
Set<String> uniq = new HashSet<>();
if(root == null){
return 0;
}
return getMaxHelper(root, uniq);
}
private static int getMaxHelper(Tree root, Set<String> uniq){
if(root == null){
return uniq.size();
}
int l = 0;
int r = 0;
if(uniq.add(root.data)){
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
uniq.remove(uniq.size()-1);
}
else{
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
}
return Math.max(l, r);
```

}

- Fa1987 March 21, 2017