Start practising

All Nodes Distance K in Binary Tree

Medium Trees & BST Child + Ancestor Handling Original on LeetCode

All Nodes Distance K in Binary Tree is a medium trees & bst problem solved with the child + ancestor handling pattern. The best approach, one dfs without a parent map, runs in O(n) time and O(h) space. Below are 2 approaches in Java, from parent map + bfs up.

Problem

Given a binary tree, a target node and an integer k, return the values of all nodes exactly k edges away from the target. Paths can go up through parents as well as down through children.

Examples

Example 1

Input
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2
Output
[7, 4, 1]

Example 2

Input
root = [1], target = 1, k = 3
Output
[]

Constraints

  • The tree has 1 to 500 nodes, unique values.
  • 0 <= k <= 1000; answer in any order.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Parent map + BFSO(n)O(n)
One DFS without a parent mapO(n)O(h)

1Parent map + BFS

TimeO(n)
SpaceO(n)

Record each node's parent so the tree becomes an undirected graph. BFS from the target for exactly k levels; the queue then holds the answer.

  1. DFS to fill parent map.
  2. BFS from target over left, right, parent with a visited set, k levels.
  3. Return the values left in the queue.
Java
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        link(root, null, parent);
        Queue<TreeNode> q = new ArrayDeque<>();
        Set<TreeNode> seen = new HashSet<>();
        q.add(target);
        seen.add(target);
        for (int d = 0; d < k && !q.isEmpty(); d++) {
            for (int i = q.size(); i > 0; i--) {
                TreeNode n = q.poll();
                for (TreeNode nb : new TreeNode[] { n.left, n.right, parent.get(n) })
                    if (nb != null && seen.add(nb)) q.add(nb);
            }
        }
        List<Integer> out = new ArrayList<>();
        for (TreeNode n : q) out.add(n.val);
        return out;
    }

    private void link(TreeNode n, TreeNode p, Map<TreeNode, TreeNode> parent) {
        if (n == null) return;
        parent.put(n, p);
        link(n.left, n, parent);
        link(n.right, n, parent);
    }
}

2One DFS without a parent map

TimeO(n)
SpaceO(h)

DFS returns the distance from a node to the target (or -1 if the target is not below it). When the target is found, collect nodes k levels below it. For each ancestor at distance d, collect nodes k - d - 1 levels down its other child, plus the ancestor itself when d == k.

  1. dist(node): if node == target, collectDown(node, k); return 0.
  2. If the left returns d >= 0: if d + 1 == k add node, else collectDown(right, k - d - 2); return d + 1. Same for the right.
  3. collectDown(n, depth) adds nodes exactly depth levels below.
Java
class Solution {
    private final List<Integer> out = new ArrayList<>();
    private TreeNode target;
    private int k;

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        this.target = target;
        this.k = k;
        dist(root);
        return out;
    }

    private int dist(TreeNode n) {
        if (n == null) return -1;
        if (n == target) { down(n, k); return 0; }
        int l = dist(n.left);
        if (l >= 0) {
            if (l + 1 == k) out.add(n.val); else down(n.right, k - l - 2);
            return l + 1;
        }
        int r = dist(n.right);
        if (r >= 0) {
            if (r + 1 == k) out.add(n.val); else down(n.left, k - r - 2);
            return r + 1;
        }
        return -1;
    }

    private void down(TreeNode n, int depth) {
        if (n == null || depth < 0) return;
        if (depth == 0) { out.add(n.val); return; }
        down(n.left, depth - 1);
        down(n.right, depth - 1);
    }
}

Edge cases to test

  • k = 0 (just the target)
  • Distance k reaches up through ancestors and down the other side

Hints

Hint 1

Nodes at distance k may be above the target. Give every node a parent pointer, then BFS k steps.

FAQ

What is the best time complexity for All Nodes Distance K in Binary Tree?

One DFS without a parent map runs in O(n) time and O(h) extra space.

Which pattern does All Nodes Distance K in Binary Tree use?

It is a trees & bst problem that uses the child + ancestor handling pattern. Other problems with the same pattern: Amount of Time for Binary Tree to Be Infected, Burning Tree.

Is there a brute force solution for All Nodes Distance K in Binary Tree?

Yes. Parent map + BFS takes O(n) time and O(n) space. Record each node's parent so the tree becomes an undirected graph.

Which edge cases should I test for All Nodes Distance K in Binary Tree?

k = 0 (just the target); Distance k reaches up through ancestors and down the other side.