# 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); } ```