Amazon Interview Question
SDE1sCountry: 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, 2014