Find Nodes at k Distance From the Root

Given the root of a binary tree and an int k with k >= 0, return the values of all nodes exactly k edges below the root (at depth k), from left to right.

Example

Text

Values inserted: 6, 4, 9, 2, 5, 8, 12, 10, 14
k = 0 -> [6]
k = 2 -> [2, 5, 8, 12]
k = 5 -> []   (the tree isn't that deep)

graph TB
    a["6 (depth 0)"] --> b["4 (depth 1)"]
    a --> c["9 (depth 1)"]
    b --> d["2 (depth 2)"]
    b --> e["5 (depth 2)"]
    c --> f["8 (depth 2)"]
    c --> g["12 (depth 2)"]
    g --> h["10 (depth 3)"]
    g --> i["14 (depth 3)"]
    style d stroke-width:3px
    style e stroke-width:3px
    style f stroke-width:3px
    style g stroke-width:3px

Brute force: record every node's depth

Traverse the entire tree, record each node's value and depth in a list of int[]{value, depth} pairs, and keep the values whose depth is k. An in-order traversal lists nodes at the same depth from left to right.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, so there are no wrapper types. The helper fromValues builds a binary search tree by inserting the values in order: smaller values go left, others go right.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        TreeNode fresh = new TreeNode(val);
        if (root == null) return fresh;
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = fresh; break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = fresh; break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) {
            root = insert(root, v);
        }
        return root;
    }

    static void depths(TreeNode root, int depth, List<int[]> out) {
        if (root == null) return;
        depths(root.left, depth + 1, out);
        out.add(new int[]{root.val, depth});
        depths(root.right, depth + 1, out);
    }

    static List<Integer> atDistance(TreeNode root, int k) {
        List<int[]> all = new ArrayList<>();
        depths(root, 0, all);
        List<Integer> result = new ArrayList<>();
        for (int[] pair : all) {
            if (pair[1] == k) result.add(pair[0]);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(atDistance(root, 0) + " " + atDistance(root, 2) + " " + atDistance(root, 5));
    }
}

Output

[6] [2, 5, 8, 12] []

Time: O(n). Space: O(n) for the list of all nodes. Every node below depth k is visited even though none of them can be part of the answer.

Optimal: DFS that stops at depth k

Pass the remaining distance down the tree. When it reaches 0, record the node and return without going deeper. Visiting left before right keeps the output in left-to-right order.

Walkthrough with k = 2:

call	remaining	action
6	2	recurse into 4 and 9 with 1
4	1	recurse into 2 and 5 with 0
2	0	record 2, stop
5	0	record 5, stop
9	1	recurse into 8 and 12 with 0
8	0	record 8, stop
12	0	record 12, stop (10 and 14 are never visited)

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        TreeNode fresh = new TreeNode(val);
        if (root == null) return fresh;
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = fresh; break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = fresh; break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) {
            root = insert(root, v);
        }
        return root;
    }

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

    static List<Integer> atDistance(TreeNode root, int k) {
        List<Integer> out = new ArrayList<>();
        collect(root, k, out);
        return out;
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(atDistance(root, 0) + " " + atDistance(root, 2) + " " + atDistance(root, 5));
    }
}

Output

[6] [2, 5, 8, 12] []

Time: O(min(n, 2ᵏ⁺¹)): only nodes at depth k or less are visited, and there are at most 2ᵏ⁺¹ - 1 of those. Space: O(k) for the recursion.

The recursion ends at k == 0 for k >= 0. A negative k would never reach 0 and would only stop at null children, returning an empty list, so the lesson treats k >= 0 as a precondition.

Alternative: BFS that stops after k levels

Process the tree level by level and return the queue's contents after k levels. ArrayDeque is a resizable array used as a queue. It rejects null, so each child is checked before it is added.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        TreeNode fresh = new TreeNode(val);
        if (root == null) return fresh;
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = fresh; break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = fresh; break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) {
            root = insert(root, v);
        }
        return root;
    }

    static List<Integer> atDistance(TreeNode root, int k) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        for (int level = 0; level < k; level++) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (TreeNode node : queue) {
            result.add(node.val);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(atDistance(root, 2) + " " + atDistance(root, 3));
    }
}

Output

[2, 5, 8, 12] [10, 14]

Time: the same as the DFS. Space: O(w) for the queue, where w is the widest level visited, with no recursion.