Return to Answer

I think your code looks good. I just found readability as issue. It can be fixed by simply rewriting the code and renaming the variables. For example, instead of using items I am using path. I have not used generics, just to focus on algorithm. Good part about your algorithm is that you have used lists (i.e. items list and visited) so you don't have to worry about sizes etc, but arrays have their own advantages as your can use indices.

Here is the code taken from kodeknight. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

// This function prints all nodes that are distance k from a leaf node
//   path[] - Store ancestors of a node
//   visited[] - Stores true if a node is printed as output.  A node may be k
//                 distance away from many leaves, we want to print it once 
void kDistantFromLeafUtil(Node node, int path[], bool visited[],
                          int pathLen, int k)
{
    // Base case
    if (node==null) return;
  
    // append this Node to the path array 
    path[pathLen] = node.key;
    visited[pathLen] = false;
    pathLen++;
  
    // it's a leaf, so print the ancestor at distance k only
       if the ancestor is not already printed  
    if (node.left == null && node.right == null &&
        pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
    {
        System.out.print(path[pathLen-k-1] + " ");
        visited[pathLen-k-1] = true;
        return;
    }
  
    // If not leaf node, recur for left and right subtrees 
    kDistantFromLeafUtil(node.left, path, visited, pathLen, k);
    kDistantFromLeafUtil(node.right, path, visited, pathLen, k);
}
  
// Given a binary tree and a nuber k, print all nodes that are k
//   distant from a leaf
void printKDistantfromLeaf(Node node, int k)
{
    int path[MAX_HEIGHT];
    bool visited[MAX_HEIGHT] = {false};
    kDistantFromLeafUtil(node, path, visited, 0, k);
}

I think your code looks good. I just found readability as issue. It can be fixed by simply rewriting the code and renaming the variables. For example, instead of using items, I would use path. Good part about your algorithm is that you have used lists (i.e. items list and visited) so you don't have to worry about sizes etc, but arrays have their own advantages as your can use indices.

kodeknight has a good solution. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

Coming on the algorithm side, I think it is more or loss same - time complexity is O(n) and space complexity is O(n).

Here is the code taken from -kodeknight. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

We will traverse through the tree, and as soon as we hit a leaf node, we will check if some node exists in path at k distance away i.e. (currPathLength - k - 1 > 0). If it exists we will print it, only if it is not already visited.

Thanks. Please post the comments in case you have some feedback.

Coming on the algorithm side, I think it is more or loss same - time complexity is \$O(n)\$ and space complexity is \$O(n)\$.

Here is the code taken from kodeknight. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

We will traverse through the tree, and as soon as we hit a leaf node, we will check if some node exists in path at k distance away i.e. (currPathLength - k - 1 > 0). If it exists we will print it, only if it is not already visited.

Here is the code taken from -kodeknight. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.

I think your code looks good. I just found readability as issue. It can be fixed by simply rewriting the code and renaming the variables. For example, instead of using items I am using path. I have not used generics, just to focus on algorithm. Good part about your algorithm is that you have used lists (i.e. items list and visited) so you don't have to worry about sizes etc, but arrays have their own advantages as your can use indices.

Coming on the algorithm side, I think it is more or loss same - time complexity is O(n) and space complexity is O(n).

From the design side, I think @ruds has given a really good solution.

Here is the code taken from -kodeknight. We can have 2 arrays - one containing the path of nodes traversed and other containing whether the present node is visited or not, as same node can be k distance from multiple leaves.