All problems

All Nodes Distance K in Binary Tree

Medium · tree bfs

You are given the root of a binary tree, the value target of one of its nodes, and a number k. The distance between two nodes is the number of edges on the path between them. A path may go down to a child or up to a parent, so the nodes above and beside the target count as well as the ones below it.

Return the values of all nodes whose distance from the target node is exactly k. The values in the tree are all different, so target identifies one node.

The values may be returned in any order. If no node is that far from the target, return an empty list []. A distance of 0 means the target node itself.

Examples

Example 1

Input: root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7], target = 6, k = 2

Output: [1, 8]

From 6, node 3 is one step up. From 3, one more step reaches 1 (down) or 8 (up). Nodes 4 and 7 are only one step away.

Example 2

Input: root = [4, 2, 6, 1, 3, 5, 7], target = 1, k = 4

Output: [5, 7]

The path from 1 goes up through 2 and 4, then down to 6 and finally to 5 or 7.

Example 3

Input: root = [9], target = 9, k = 0

Output: [9]

A distance of 0 is the target itself.

Constraints