LeetCode 863: All Nodes Distance K in Binary Tree Solution

Master LeetCode problem 863 (All Nodes Distance K in Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

863. All Nodes Distance K in Binary Tree

Medium

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation

To find all nodes at a distance k from a target node in a binary tree, we can start by performing a depth-first search (DFS) to find the path from the root to the target node. During this process, we can record the parent nodes for each node to facilitate backtracking later. Once we have found the target node, we can perform a second DFS starting from the target node to explore nodes at a distance k.

Perform DFS to find the path from the root to the target node and record parent nodes.
Perform a second DFS from the target node to find nodes at distance k.

Solution Code

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> result = new ArrayList<>();
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Set<TreeNode> visited = new HashSet<>();

        findParentNodes(root, null, parent);

        findNodesAtDistanceK(target, k, parent, result, visited);

        return result;
    }

    private void findParentNodes(TreeNode node, TreeNode parentNode, Map<TreeNode, TreeNode> parent) {
        if (node == null) return;
        parent.put(node, parentNode);
        findParentNodes(node.left, node, parent);
        findParentNodes(node.right, node, parent);
    }

    private void findNodesAtDistanceK(TreeNode node, int k, Map<TreeNode, TreeNode> parent, List<Integer> result, Set<TreeNode> visited) {
        if (node == null || visited.contains(node)) return;

        visited.add(node);

        if (k == 0) {
            result.add(node.val);
            return;
        }

        findNodesAtDistanceK(node.left, k - 1, parent, result, visited);
        findNodesAtDistanceK(node.right, k - 1, parent, result, visited);
        findNodesAtDistanceK(parent.get(node), k - 1, parent, result, visited);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 863 (All Nodes Distance K in Binary Tree)?

This page provides optimized solutions for LeetCode problem 863 (All Nodes Distance K in Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 863 (All Nodes Distance K in Binary Tree)?

The time complexity for LeetCode 863 (All Nodes Distance K in Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 863 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 863 in Java, C++, or Python.

Back to LeetCode Solutions