Amazon Interview Question SDE1s
Country: United States
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.
I think your solution will not work,beacuse it is not mentioned that all the leaves are on the same level.
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.
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);
}
}
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);
}
}
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)
kthNodes.add(start);
else if(start.items!=null){ i++;
//System.out.println(start.data+" "+start.items.length);
for(Box b:start.items)
find(b,i);
}
}
}
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);
}
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;
}
}
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)
Fixed Solution:
- guilhebl February 16, 2014import 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; } public void addChild(Node child) { if(childs == null) { childs = new ArrayList<Node>(); } childs.add(child); } @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"); root.addChild(n2); root.addChild(n3); root.addChild(n4); Node na = new Node(); na.setData("a"); Node nb = new Node(); nb.setData("b"); n2.addChild(na); n2.addChild(nb); Node nc = new Node(); nc.setData("c"); n3.addChild(nc); Node nd = new Node(); nd.setData("d"); Node ne = new Node(); ne.setData("e"); n4.addChild(nd); n4.addChild(ne); 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"); root.addChild(n2); root.addChild(n3); root.addChild(n4); Node na = new Node(); na.setData("a"); Node nb = new Node(); nb.setData("b"); n2.addChild(na); n2.addChild(nb); Node na1 = new Node(); na1.setData("a1"); na.addChild(na1); Node nc = new Node(); nc.setData("c"); n3.addChild(nc); Node nd = new Node(); nd.setData("d"); Node ne = new Node(); ne.setData("e"); n4.addChild(nd); n4.addChild(ne); Node nc1 = new Node(); nc1.setData("c1"); nc.addChild(nc1); Node nc2 = new Node(); nc2.setData("c2"); nc.addChild(nc2); Node nc11 = new Node(); nc11.setData("c11"); nc1.addChild(nc11); Node nc12 = new Node(); nc12.setData("c21"); nc1.addChild(nc12); 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(); } }