DSA interview question

All Nodes at Distance K in a Binary Tree

Hard · Data structures · Topics: tree, dfs, bfs

The problem

A social app stores a referral tree (each user points to the users they invited), and a campaign wants every user exactly K hops away from a given user, counting links in both directions: up to the inviter as well as down to invitees. Tree nodes only point down, so first record each node's parent. Then the tree is effectively an undirected graph, and a BFS from the target that stops after K levels, never revisiting a node, collects exactly the nodes at distance K.

Example: tree [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target 5, K = 2 → [1, 4, 7].

Function signature

vector<int> distanceK(TreeNode* root, TreeNode* target, int k);  // shown sorted here

Test cases

Input `(tree, target, K)`	Output (sorted)	Explanation
`([3,5,1,6,2,0,8,null,null,7,4], 5, 2)`	`[1, 4, 7]`	7 and 4 below, 1 via the root
`([3,5,1,6,2,0,8,null,null,7,4], 5, 0)`	`[5]`	Distance 0 is the target itself
`([3,5,1,6,2,0,8,null,null,7,4], 3, 3)`	`[4, 7]`	The deepest level
`([3,5,1,6,2,0,8,null,null,7,4], 7, 3)`	`[3, 6]`	Up two, then across or up again
`([1], 1, 3)`	`[]`

(Confirm: node values are unique; distance counts edges in either direction; any output order is fine.)

How interviewers phrase it

"Given the root of a binary tree, a target node and an integer k, return the values of all nodes at distance k from the target" (LeetCode 863).

Clarifying questions to ask

Can the path go up through ancestors? (Yes.)
Are values unique? (Yes, which makes sets of values safe.)
Does the output order matter? (No.)

Follow-ups to expect

"Why record parent pointers?"
"Why a visited set?"
"DFS-only alternative?"
"What about the burning tree problem?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview