All Nodes Distance K in Binary Tree
On this page
Problem statement
Given the root of a binary tree, a target node in it, and an integer k, return the values of all nodes that are exactly k edges away from the target. Paths may go up through parents as well as down through children. Node values are unique; return them in any order.
The twist is the word "up": tree code usually only walks down. The fix is to treat the tree as an undirected graph, and then the problem becomes an ordinary BFS. Original problem: LeetCode 863.
Example

Tree: 8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
target = 3, k = 2 -> [4, 7, 10]
target = 3, k = 0 -> [3]
target = 13, k = 3 -> [8] # 13 -> 14 -> 10 -> 8
Constraints (assumed)
- 1 ≤ number of nodes ≤ 500; values are unique.
- 0 ≤ k ≤ 1,000 (k may be larger than the tree's height, in which case the answer can be empty).
What this question tests
- Noticing that a tree is a graph once you allow moving to the parent.
- Adding parent pointers (or an adjacency list) in one traversal.
- Writing a level-by-level BFS with a visited set.
Questions to ask first
- Do nodes have a parent pointer? (Here: no, only left and right.)
- Is the target given as a node or as a value? (Here: a node. If it's a value, find it first.)
- Are values unique? (Here: yes, so a set of values works as "visited" too.)
- Any order for the answer? (Here: yes.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.