Abstract / Summary

Given a tree and a node and a distance, return all nodes that are that distance away from the given node.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (1+ million submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation defines a method that, given a binary tree, a target node, and an integer k, returns the values of all nodes whose distance from the target equals k. It first converts the tree into an undirected graph where each node is connected to its parent and children, then performs a breadth-first search (BFS) from the target for exactly k steps, collecting the frontier nodes.

Edge Construction

A nested helper, deeper, walks the tree recursively. For every non-null node it records a bidirectional edge between the node’s value and its parent’s value (when a parent exists). The adjacency information is stored in a defaultdict(set) called edges. Because the graph is undirected, each connection is added in both directions, enabling traversal upward toward the root as well as downward toward the leaves.

edges = defaultdict(set)

def deeper(node, parentVal):
    if not node:
        return

    if parentVal is not None:
        edges[node.val].add(parentVal)
        edges[parentVal].add(node.val)

    deeper(node.left,  node.val)
    deeper(node.right, node.val)

deeper(root, None)

The recursion stops automatically when a leaf’s child is None, so the function gracefully handles empty subtrees and an entirely empty tree.

BFS Traversal

After the graph is built, the algorithm initializes a frontier set todo containing only the target’s value. A second set have tracks nodes that have already been visited. For each of the k iterations, a new frontier next is created by taking the union of all neighbors of the current frontier (edges[t]) and then removing any nodes already seen (- have). The current frontier nodes are added to have before the next step, guaranteeing that each node is processed at most once. When the loop finishes, todo holds exactly the nodes that lie at distance k from the target, and the method returns them as a list.

todo = set([target.val])
have = set()
for steps in range(k):
    next = set()
    for t in todo:
        have.add(t)
        next |= edges[t] - have
    todo = next

return list(todo)

If k is zero, the loop body never executes and the method returns a list containing only the target’s value, correctly handling the zero-distance case.

Edge Cases Handled

The code naturally accommodates several boundary conditions:

• An empty tree (root is None) results in edges remaining empty; the BFS loop operates on an empty adjacency map, and the final list will be empty unless k is zero and the target is also None, which is not a typical input scenario.
• A target node that is a leaf has only one neighbor (its parent). The BFS still expands correctly because the adjacency set for the leaf contains that single parent.
• When the target is the root, the parent edge is never added, leaving only child connections; the BFS proceeds outward through the children without attempting to reference a non-existent parent.
• A value of k greater than the height of the tree leads the frontier to become empty before the loop ends; subsequent iterations operate on an empty set, and the final result is an empty list, reflecting that no nodes exist at that distance.
• Duplicate values are impossible in a proper binary tree, and the use of sets for both adjacency and visited nodes guarantees that each node value is processed only once, even if the tree contains repeated structural patterns.

Performance Optimizations

The implementation leverages several techniques to keep the execution efficient:

• The adjacency list is built with defaultdict(set), allowing constant-time insertion of edges and eliminating the need for explicit existence checks.
• By storing node values rather than node objects in the graph, the algorithm reduces memory overhead and simplifies set operations.
• The BFS frontier and visited collections are both sets, enabling O(1) membership tests and fast set difference (edges[t] - have) to filter out already visited nodes without scanning a list.
• The use of the in-place union operator (|=) accumulates neighbor nodes for the next level in a single step, avoiding the creation of intermediate list structures.
• The loop iterates exactly k times, and each iteration processes only the current frontier, so the work performed is proportional to the number of nodes within distance k from the target rather than the entire tree. This localized processing avoids unnecessary traversal of unrelated subtrees.

Imagine a big family tree where every person is holding hands with their parents and their children. Sometimes it is hard to move around this tree because you can only walk down to the children. First, the code walks through the whole tree and records every hand-holding connection. Now, everyone is connected to the people above them and the people below them, which makes the tree look more like a map with many paths.

Next, the code starts at the target person that you picked. It looks at everyone standing exactly one hand-hold away and keeps track of them. Then it looks for everyone standing two hand-holds away, and keeps doing that until it reaches the number of steps that was asked for. It uses a helper list to make sure nobody gets counted twice, just like making sure you do not visit the same friend twice while you are exploring. By the end of this process, the code has found all the people hiding at that exact distance away.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python								TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python						Go		TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem							Ruby
	gouthampradhan		Java
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	MacJim	C++
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vli02										C
	wisdompeak	C++
	yuanliu666								Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality