Amazon Interview Question
Dev Leads Dev LeadsTeam: Software development engineer II
Country: United States
Interview Type: Phone Interview
How about using an ArrayList instead of a stack? That way you can find the appropriate parent desired. Then track results with a HashSet.
public static TreeNode[] getNParent(TreeNode node, int generation){
//bad inputs
if(node == null){
return null;
}
if(generation < 1){
throw new IllegalArgumentException();
}
//tracking values
ArrayList<TreeNode> results= new ArrayList<TreeNode>();
getNParent(node, results, generation);
return results.toArray(new int[results.size()]);
}
private static int getNParent(TreeNode node, ArrayList<TreeNode> results, int generation){
int left = 0;
if(node.left != null){
left = getNParent(node.left, results, generation);
}
int right = 0;
if(node.right != null){
right = getNParent(node.right, results, generation);
}
if(left == generation || right == generation){
results.add(node);
}
return (left > right)? left+1 : right+1;
}
public static void PrintTreeAndLastNodes(Tree root, int n)
{
Stack<Tree> stack = new Stack<Tree>();
int count = 0;
while (true)
{
// while a tree
while (root != null)
{
stack.Push(root);
root = root.Left;
}
if (stack.Count == 0)
break;
if (stack.Count > 0)
{
root = stack.Pop();
if (root.Right == null && root.Left == null)
{
//This is a Lead Node we need to capure
}
else
{
count++;
if (count == n)
{
count = 0;
Console.WriteLine(root.data);
}
}
root = root.Right;
}
}
}
depth of node = max( depth of node->lChild , depth of node-> rChild) +1
when it is equal to n then print value. base algo can be
int Tree::TreeDepth(treePtr root)
{
if(!root)
return 0;
else
{
int lDepth=TreeDepth(root->lChild);
int rDepth=TreeDepth(root->rChild);
int currDepth;
if(lDepth>rDepth)
currDepth = lDepth+1;
else
currDepth = rDepth+1;
if(currDepth==N)
cout <<root->value<<endl;
return currDepth;
}
}
BFS is the right choice because you want to get all nodes in same level. DFS goes to deep first, not the nodes in the same level. And you should use a queue.
Below code while making BFS, when reached to the specified level, breaks from the loop.
So we have only the specified level in the queue. We print them.
I used classical node and some aux variable to keep track of current level. But may be putting level info to Node class can be more readable choice. But this time for every node we have to add an integer to every node.
private static void findLengthTree(Node root,int printLevel ) {
int currentLevel = 0;
String levelStart = "";
Node currentNode = null;
LinkedList<Node> child = new LinkedList<>();
child.add(root);
levelStart = root.data;
while(!child.isEmpty()) {
currentNode = child.peek();
if(levelStart == "" || currentNode.data == levelStart) {
if(currentLevel == printLevel)
break;
if(currentNode.left !=null) {
levelStart= currentNode.left.data;
currentLevel++;
}
else if(currentNode.right != null) {
levelStart= currentNode.right.data;
currentLevel++;
}
else levelStart = "";
}
child.poll();
if(currentNode.left !=null)
child.add(currentNode.left);
if(currentNode.right != null)
child.add(currentNode.right);
}
System.out.println("Data in level:" + printLevel);
while(!child.isEmpty()) {
System.out.println(child.poll().data);
}
}
It says going from leaf node up to a certain level, not from the root down to the certain level. If you use BFS, you won't know which level it is above the leaf node.
The question is not clear at all. Can you explain in clear English.
- random September 19, 2014