All Nodes Distance K in Binary Tree

Navigate to Other Languages

Problem Description

Imagine you’re at a family reunion, and you want to find out which relatives are standing exactly K feet away from you. Sounds simple, right? Well, welcome to the world of binary trees, where things get a bit more complicated!

In the LeetCode problem “All Nodes Distance K in Binary Tree,” you are given a binary tree and a target node. Your mission, should you choose to accept it, is to find all nodes that are exactly K distance away from the target node. Think of it as trying to find all your cousins who are just far enough away that you can’t hear their embarrassing stories, but close enough that you can still wave at them.

Code Solution


class Solution {
  public List distanceK(TreeNode root, TreeNode target, int k) {
    List ans = new ArrayList<>();
    Map nodeToDist = new HashMap<>(); // {node: distance to target}

    getDists(root, target, nodeToDist);
    dfs(root, k, 0, nodeToDist, ans);

    return ans;
  }

  private void getDists(TreeNode root, TreeNode target, Map nodeToDist) {
    if (root == null)
      return;
    if (root == target) {
      nodeToDist.put(root, 0);
      return;
    }

    getDists(root.left, target, nodeToDist);
    if (nodeToDist.containsKey(root.left)) {
      nodeToDist.put(root, nodeToDist.get(root.left) + 1);
      return;
    }

    getDists(root.right, target, nodeToDist);
    if (nodeToDist.containsKey(root.right))
      nodeToDist.put(root, nodeToDist.get(root.right) + 1);
  }

  private void dfs(TreeNode root, int k, int dist, Map nodeToDist,
                   List ans) {
    if (root == null)
      return;
    if (nodeToDist.containsKey(root))
      dist = nodeToDist.get(root);
    if (dist == k)
      ans.add(root.val);

    dfs(root.left, k, dist + 1, nodeToDist, ans);
    dfs(root.right, k, dist + 1, nodeToDist, ans);
  }
}

Approach Explanation

The solution employs a two-step approach:

  1. Distance Calculation: The getDists method calculates the distance of each node from the target node and stores it in a map. This is like measuring how far each relative is from you at the reunion.
  2. Depth-First Search (DFS): The dfs method traverses the tree to find nodes that are exactly K distance away from the target. It’s like walking through the crowd and checking who’s within your waving range.

Time and Space Complexity

Complexity Analysis
Time Complexity O(N), where N is the number of nodes in the tree. We traverse each node once to calculate distances and again to find nodes at distance K.
Space Complexity O(N) for the map that stores distances and the list that stores the result.

Real-World Example

Let’s say you’re at a family reunion, and you want to find all your cousins who are exactly 3 feet away from you. You first measure the distance of each cousin (node) from you (target) and then check who is exactly 3 feet away. This is exactly what the algorithm does with the binary tree!

Similar Problems