## Amazon Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Fixed Solution:

``````import java.util.*;

public class PrintAllNodesDistanceKFromLeaves {

class Node {
private List<Node> childs;
private String data;

public String getData() {
return data;
}
public void setData(String d) {
this.data = d;
}
public List<Node> getChilds() {
return childs;
}
if(childs == null) {
childs = new ArrayList<Node>();
}
}

@Override
public String toString() {
return data;
}
}

/**
* Winds back to K from leaf node until it reaches a node which diff from K is 0
*
* @param root
* @param k
* @return diff from K
*/
public int getDistanceKFromLeaf(Node root, int k) {
// is leaf
if (root == null || root.getChilds() == null || root.getChilds().isEmpty()) {
return k-1;
}

int distKMin = Integer.MAX_VALUE;
boolean printed = false;
if (root.getChilds() != null && !root.getChilds().isEmpty()) {
for (Node child : root.getChilds()) {
int distK = getDistanceKFromLeaf(child, k);

if (distK == 0 && !printed) {
System.out.println(root.getData());
}

if (distK > 0 && distK < distKMin) {
distKMin = distK;
}
}
}

return distKMin - 1;
}

/*
* 1) Test scenario 1: balanced tree
*
* Sample Tree:
* 			1
2           3         4
a   b           c         d e
*/
public Node buildTestTree() {

Node root = new Node();
root.setData("1");

Node n2 = new Node();
n2.setData("2");

Node n3 = new Node();
n3.setData("3");

Node n4 = new Node();
n4.setData("4");

Node na = new Node();
na.setData("a");

Node nb = new Node();
nb.setData("b");

Node nc = new Node();
nc.setData("c");

Node nd = new Node();
nd.setData("d");

Node ne = new Node();
ne.setData("e");

return root;
}

/*
* 1) Test scenario 2: unbalanced tree
*
* Sample Tree:
* 			1
2           3         4
a   b           c         d e
a1			c1	c2
c11	c12
*/
public Node buildTestTree2() {

Node root = new Node();
root.setData("1");

Node n2 = new Node();
n2.setData("2");

Node n3 = new Node();
n3.setData("3");

Node n4 = new Node();
n4.setData("4");

Node na = new Node();
na.setData("a");

Node nb = new Node();
nb.setData("b");

Node na1 = new Node();
na1.setData("a1");

Node nc = new Node();
nc.setData("c");

Node nd = new Node();
nd.setData("d");

Node ne = new Node();
ne.setData("e");

Node nc1 = new Node();
nc1.setData("c1");

Node nc2 = new Node();
nc2.setData("c2");

Node nc11 = new Node();
nc11.setData("c11");

Node nc12 = new Node();
nc12.setData("c21");

return root;
}

public void execute() {
Node root = buildTestTree();
getDistanceKFromLeaf(root, 2);

System.out.println(" \n------------------\n ");

Node root2 = buildTestTree2();
getDistanceKFromLeaf(root2, 2);
}

public static void test() {
PrintAllNodesDistanceKFromLeaves solution = new PrintAllNodesDistanceKFromLeaves();
solution.execute();
}
}``````

Comment hidden because of low score. Click to expand.
0

Nope. There can be several nodes in a tree which are a distance k from the max level but a distance less than k from their leaf node.

Comment hidden because of low score. Click to expand.
0

I think your solution will not work,beacuse it is not mentioned that all the leaves are on the same level.

Comment hidden because of low score. Click to expand.
0

That's right, please check the new fixed version of the algorithm, I tested with both scenarios: balanced and unbalanced tree, both is working, let me know if you find any other bug, please also notice the statement doesn't explicitly tell it's a binary tree, so assuming a N-ary tree

Comment hidden because of low score. Click to expand.
0
of 0 vote

Post-order traverse for the tree, calculate all depths in left tree (e.g., 3, 4), and all depths in right tree (e.g., 2, 3), and combine the results into one list (2, 3, 4), then add '1' to each elements, we will have (3, 4, 5), and get back to parent node.

If 'k' is in the new list, or 'k-1' is in the combined list, output the current node.

Comment hidden because of low score. Click to expand.
0

close. What we can do, is traverse the tree (post order) and for each parent node calculate its height h (i.e Max of height of left and right subtrees). Then if h ==k, print the parent node.

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public void levelTraversal(Tree root, int level) {
if (root == null) {
return;
}
if (level == 1) {
System.out.print(root.value + "->");
} else {
levelTraversal(root.left, level - 1);
levelTraversal(root.right, level - 1);
}
}``````

Comment hidden because of low score. Click to expand.
0

this will more likely print the nodes at distance k from root , not from leaf

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int findHeight(TreeNode root) {
if(root == null || (root.left == null && root.right == null))
return 0;
else
return Math.max(findHeight(root.left), findHeight(root.right))+1;
}
public static void findNodesKFromLeaf(TreeNode root, int k) {
if(root == null)
return;

findNodesKFromLeaf(root.left,k);
findNodesKFromLeaf(root.right,k);

int lefth = findHeight(root.left);
int righth = findHeight(root.right);

if(Math.max(lefth, righth) +1  == k) {
System.out.println(root.value);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````struct distk {
int k1;
int k2;
}

distk printnodek( node *root, int k) {
if (root == NULL)
return k;

struct dk;
dk.k1 = printnodek(root->left, k);
dk.k2 = printnodek(root->right,k);
if (dk.k1==0 || dk.k2==0)
printf("Node was %d", root->data);
dk.k1--;
dk.k2--;
return dk;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

class Box{
Box(String data, Box list[]){
this.data=data;
this.items=list;
}
String data;
Box items[] ;
}

public class TreeStructure {
static ArrayList<Box> kthNodes= new ArrayList();
public static void main(String[] args) {
Box items1[]={new Box("2",null),new Box("2",null)};
Box items2[]={new Box("2",null),new Box("2",null)};
Box items[]={new Box("1",items1),new Box("1",items2)};
Box start= new Box("root",items);
findKNodes(start);
for(Box b:kthNodes)
System.out.println("Data is "+b.data);
}
private static void findKNodes(Box start) {
find(start,0);
}

private static void find(Box start, int i) {
if(start==null)
return;
if(i==2)
else if(start.items!=null){ i++;
//System.out.println(start.data+" "+start.items.length);
for(Box b:start.items)
find(b,i);
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findKDistantLeafNodes(TreeNode root, int k) {

if(root == null) return;

// non leaf

if( reachableToLeafNode(root, k) ) {

System.out.print("** " + root.data + " **");

}

findKDistantLeafNodes(root.left, k);
findKDistantLeafNodes(root.right, k);
}

public static boolean reachableToLeafNode(TreeNode root, int k) {

if (root == null) return false;

if (root.left == null && root.right == null && k ==0 ) return true;

return reachableToLeafNode(root.left, k -1) || reachableToLeafNode(root.right, k -1);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

static void printFromLeaf(TreeNode root, int k)
{
if(root == null)
return;

printFromLeaf(root.getLeft(), k);
printFromLeaf(root.getRight(), k);

int leftHeight = getHeight(root.getLeft());
int rightHeight = getHeight(root.getRight());

if(leftHeight+1 == k || rightHeight+1 == k)
System.out.printf(" "+ root.data);

}

static int getHeight(TreeNode root)
{
if(root == null || (root.getLeft() == null && root.getRight() == null))
return 0;
else
{
return Math.max(getHeight(root.getLeft()),getHeight(root.getRight()))+1;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Write a recursive function to calculate the height , if height(node) = k , push them into a stack
finally pop out everything from the stack
( Note take height of leaf node =0)
------------- Time Complexity : O(n)
------------ Space Complexity : O(1)

Optimed solution for time :-
memoize the recursion
i.e - store the heights of every node you calculate in a hash table
and then check first if the hash map has a value of height for this node in recursion
if present return the value from hash map , else do the recursion
Time Complexity ------------- O(n)
Space Complexity ----------- O(n)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.