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
Hiring now
Get the Amazon interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question