# Leetcode 863. All Nodes Distance K in Binary Tree
###### tags: `Leetcode`
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
## Description
We are given a binary tree (with root node root), a target node, and an integer value K.
Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.
**Example 1:**
```
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation:
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.
```

```
Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.
```
**Example 2:**
```
Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.
```
**Note:**
- The given tree is non-empty.
- Each node in the tree has unique values 0 <= node.val <= 500.
- The target node is a node in the tree.
- 0 <= K <= 1000.
## Solution in C
Time Complexity: $O(n)$
Space Complexity: $O(n)$
```c
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* distanceK(struct TreeNode* root, struct TreeNode* target, int K, int* returnSize) {
int *q = malloc(100*sizeof(int));
getTargetDepth(root,target,K,returnSize,q);
return q;
}
int getTargetDepth(struct TreeNode* root, struct TreeNode* target, int K, int* returnSize, int *q){
if (root==NULL)
return -1;
if (root==target){
push(root,K,returnSize,q);
return 0;
}
int l = getTargetDepth(root->left ,target,K,returnSize,q);
int r = getTargetDepth(root->right,target,K,returnSize,q);
if (l!=-1){
if (K-l-1==0){
q[(*returnSize)]=root->val;
(*returnSize)++;
}
push(root->right,K-l-2,returnSize,q);
return l+1;
}
else if (r!=-1){
if (K-r-1==0){
q[(*returnSize)]=root->val;
(*returnSize)++;
}
push(root->left,K-r-2,returnSize,q);
return r+1;
}
return -1;
}
void push(struct TreeNode* root, int K, int* returnSize, int *q){
if (root==NULL || K<0) return;
if (K==0){
q[(*returnSize)]=root->val;
(*returnSize)++;
return;
}
push(root->left ,K-1,returnSize,q);
push(root->right,K-1,returnSize,q);
}
```