// function to calculate height of binary tree that is used to define the lenght of ancestor path array and boolean array.
private static int heightBT(Node root){
if(root == null) return 0;
int l = heightBT(root.left);
int r = heightBT(root.right);
return ((l>r)?l:r) + 1;
}
private static void allNodesfromLeafUtil(Node root, int k, int path[], int visited[], int pathlen){
if(root == null) return;
// keep storing all ancestors till we hit a leaf node also keep tracking the nodes that are already printed for that we use a boolean array visited[].
path[pathlen] = root.data;
visited[pathlen] = 0;
pathlen++;
if(root.left == null && root.right == null && pathlen-k-1 >= 0 && visited[pathlen-k-1] == 0)
{
System.out.println(path[pathlen-k-1]);
visited[pathlen-k-1] = 1;
return;
}
allNodesfromLeafUtil(root.left, k, path, visited, pathlen);
allNodesfromLeafUtil(root.right, k, path, visited, pathlen);
}
static void allNodesfromLeaf(Node root, int k){
int pathlen = 0;
int height = heightBT(root);
int path[] = new int[height];
int visited[] = new int[height];
allNodesfromLeafUtil(root, k, path, visited, pathlen);
}
No comments:
Post a Comment