---
# System prepended metadata

title: Leetcode 863. All Nodes Distance K in Binary Tree
tags: [Leetcode]

---

# 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.

```
![](https://i.imgur.com/DdU0ZC3.png)
```
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);
}
```