Problem statement

Given the root of a binary tree and an integer k, return the values of all nodes that are exactly k edges below the root (the root itself is at distance 0), from left to right. If the tree has no node that deep, return an empty list.

Example 1

Input: root = [1,2,3,4,5,8], k = 2
Output: [4,5,8]
Explanation: Two levels below the root sit 4, 5 and 8.

Example 2

Input: root = [1,3,2], k = 0
Output: [1]
Explanation: Distance 0 is the root itself.

Example 3

Input: root = [1,2,3], k = 3
Output: []
Explanation: The tree has no level three steps down.

Constraints

• 1 <= number of nodes <= 10^4
• 1 <= Node.val <= 10^5
• 0 <= k <= 30

Hints for Nodes at Distance K from Root

1. Hint 1

   The nodes at distance k are exactly one level of the tree.

2. Hint 2

   Walk down depth-first with a counter of how many steps remain; when it reaches 0, record the node and stop descending.

3. Hint 3

   Visiting the left child before the right one yields the level from left to right.

How to solve Nodes at Distance K from Root

Distance from the root is depth, so the answer is level k. A depth-first walk that counts down the remaining steps reaches every node of that level, left subtree before right, and never goes deeper.

Approach

1. Call collect(root, k).
2. In collect(node, steps): return if node is null; if steps == 0, append node.val and return.
3. Otherwise call collect(node.left, steps - 1) then collect(node.right, steps - 1).

Why it works

A node is reached with steps == 0 exactly when it is k edges below the root. Because every left subtree is finished before its right sibling starts, nodes of the same level are appended in left-to-right order.

Complexity

• Time — O(n) in the worst case (only nodes at depth ≤ k are visited)
• Space — O(k) for the recursion

Pitfalls

• Stop at depth k — descending further wastes time and could add deeper nodes by mistake.
• A level-order traversal works too: return the k-th level, or an empty list if the queue runs dry first.

Reference solution

Python

from typing import List, Optional

def kDistance(root: Optional[TreeNode], k: int) -> List[int]:
    out = []

    def collect(node: Optional[TreeNode], steps: int) -> None:
        if node is None:
            return
        if steps == 0:
            out.append(node.val)
            return
        collect(node.left, steps - 1)
        collect(node.right, steps - 1)

    collect(root, k)
    return out

Java

public static int[] kDistance(TreeNode root, int k) {
    List<Integer> out = new ArrayList<>();
    collect(root, k, out);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

static void collect(TreeNode node, int steps, List<Integer> out) {
    if (node == null) return;
    if (steps == 0) { out.add(node.val); return; }
    collect(node.left, steps - 1, out);
    collect(node.right, steps - 1, out);
}

C++

void collect(TreeNode* node, int steps, vector<int>& out);

vector<int> kDistance(TreeNode* root, int k) {
    vector<int> out;
    collect(root, k, out);
    return out;
}

void collect(TreeNode* node, int steps, vector<int>& out) {
    if (!node) return;
    if (steps == 0) { out.push_back(node->val); return; }
    collect(node->left, steps - 1, out);
    collect(node->right, steps - 1, out);
}

JavaScript

var kDistance = function(root, k) {
    var out = [];
    collect(root, k, out);
    return out;
};

var collect = function(node, steps, out) {
    if (node === null) return;
    if (steps === 0) { out.push(node.val); return; }
    collect(node.left, steps - 1, out);
    collect(node.right, steps - 1, out);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy