Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
class LocalBST extends BinarySearchTree
{
private class QNode{
Node node;
int level;
QNode(Node n, int level)
{
this.node=n;
this.level=level;
}
}
public int levelWithMaxNodes()
{
int maxCount=0, maxLevel=0;
Queue<QNode> qu= new LinkedList<QNode>();
qu.add(new QNode(root,0));
int levelCount=0, prevLevel=0;
while(!qu.isEmpty())
{
QNode qNode = qu.remove();
if(qNode.level>prevLevel)
{
levelCount=0;
}
levelCount+=1;
if(levelCount>maxCount)
{
maxCount=levelCount;
maxLevel=qNode.level;
}
maxCount=Math.max(levelCount, maxCount);
if (qNode.node.left!=null)
qu.add(new QNode(qNode.node.left,qNode.level+1));
if (qNode.node.right!=null)
qu.add(new QNode(qNode.node.right,qNode.level+1));
prevLevel=qNode.level;
}
return maxLevel;
}
}
- 511narender March 08, 2017