Nodes at a distance k from tar

#1

I have few doubts in the code.

    if (L != -1)
{
    if (L == k)
        cout << root->data << endl;

    KthLevel(root->right, k - L - 1);
    return 1 + L;
}

Unable to understand this chunk of code.
Why check for -1?
Why are we doing L == K
why are we returning 1+L

#2

@sounakume You are missing one condition in code, function should return -1, if both L and R are -1. and this node is not target.
Now we are checking for -1, cause we are returning -1, if root becomes null, now leaf will return -1, if it is not tar, if the parent of leaf gets -1 from both side and it is not tar then it is also return -1.
-1 indicates that tar is not present in the subtree called.
we check L, and R are distance of ancestors of tar from it, so when L==k, it means this ancestor is at distance K.
Once we are at an ancestor or tar, we move to the node at distance k-l-1 in opposite direction, as both will add up to k, and distance will become K.
I would suggest you do a dry run of the code create a tree on paper and see how values are modified and nodes printed it will help you
If this resolve your doubt mark it as resolved.

1 Like