Workspace

Problem workspace

3 day streakD

Nodes at Distance K

MediumTreesPaths & ancestors

The challenge

Return values of all nodes exactly k edges from the target node.

Target identity matters when values repeat. A missing target, negative k, or empty tree gives [].

Example

From B:4 at k = 2, the balanced example returns [12]. A distance beyond the tree gives [].

Use the walkthrough below to inspect the input and each state change.

See Distance K, step by step

Follow the branches. Watch the state change.

7 input nodes · Target: B:4 · k = 2L = left · R = right
Inspect the input.Labels identify node objects; numbers are their values. Left and right child pointers define the tree. Node labels identify objects; numbers show their values. The pointer table below provides the same structure in text.LRLRLR2D4B6E8A · root10F12C14G
CurrentProcessedPending
View child pointers & node state
Node state · null means no child
NodeValueLeftRightState
A8BC—
B4DE—
C12FG—
D2nullnull—
E6nullnull—
F10nullnull—
G14nullnull—
Step 01 / 7

Inspect the input.

Labels identify node objects; numbers are their values. Left and right child pointers define the tree.

root = A:8
View original input

A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]

Target: B:4 · k = 2

Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.

Put it into code

Build upward links, then use BFS with a visited set.

Nodes store value, left, and right. C++ uses C++17 or later.

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def distance_k(root, target, k):
    if root is None or target is None or k < 0:
        return []
    parent, stack = {root: None}, [root]
    while stack:
        node = stack.pop()
        for child in (node.left, node.right):
            if child:
                parent[child] = node
                stack.append(child)
    if target not in parent:
        return []
    queue, seen = deque([target]), {target}
    for _ in range(k):
        if not queue:
            return []
        for _ in range(len(queue)):
            node = queue.popleft()
            for nxt in (node.left, node.right, parent[node]):
                if nxt is not None and nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
    return [node.value for node in queue]

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap