Print all nodes at a distance of K in BT
Amazon
UberThe problem
Given the root of a binary tree, the value of a target node target, and an integer k. Return an array of the values of all nodes that have a distance k from the target node.
The answer can be returned in any order (N represents null).
**Note: **Although input shows target as a value, internally it refers to the TreeNode with that value.
Input : root = [3, 5, 1, 6, 2, 0, 8, N, N, 7, 4] , target = 5, k = 2 Output : [1, 4, 7] Explanation : The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Input : root = [3, 5, 1, 6, 2, 0, 8, N, N, 7, 4] , target = 5, k = 3 Output : [0, 8] Explanation : The nodes that are a distance 3 from the target node (with value 5) have values 0, 8.
Input : root =[1, 2, 3, 4, null, 5, 6], target = 6, k = 2
- 1 <= Number of Nodes <= 103
- -104 <= Node.val <= 104
- All the values Node.val are unique.
- target is the value of one of the nodes in the tree
- 0 <= k <= 103
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k){
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def distanceK(self, root, target, k):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
distanceK(root, target, k) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
*/
public class Solution
{
public IList<int> distanceK(TreeNode root, TreeNode target, int k)
{
//your code goes here
}
}go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Data int
* Left *TreeNode
* Right *TreeNode
* }
*/
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
}Stuck? Show a way to structure it+
- 01Build parent links while locating the target.
- 02Run BFS outward from the target.
- 03Visit left, right, and parent neighbors once.
- 04Collect the frontier at distance k.
Reference answer
Then expect these follow-ups
How would you answer many target-and-k queries?
Tests: tree indexing
Can recursion solve it without parent maps?
Tests: distance propagation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question