The O(n) Club: Nodes at Distance K in Binary Trees — Now With Bonus Parent Trouble

The O(n) Club: Nodes at Distance K in Binary Trees — Now With Bonus Parent Trouble

⚡ TL;DR

You need all nodes exactly K edges away from your chosen node. Not just in the subtree—up, down, sideways, through your uncle’s second cousin’s boss. The trick: turn the tree into a graph using parent pointers, then BFS out like a networking pro. Brute force? It works, if you have infinite patience and stack space:

// Brute-force version (pre-coffee):
// 1. Explore down from target for K levels.
// 2. At each parent, search child subtrees not going back down the path you came.
// Spoiler: You'll cry at node count > 1,000.

🧠 How Devs Usually Mess This Up

Look, everyone’s first instinct is to go down from the target. Feels safe. Feels right. Feels wrong, frankly—but hey, we all liked recursion once. Forgetting to look up the tree is classic. Also, TreeNode doesn’t come with a parent reference out of the box, so this ‘search up’ idea fizzles unless you map parents first. Last classic flub: mixing up ‘distance’ for ‘depth’. Edge count, not levels, folks.

🔍 What’s Actually Going On

Picture a groggy robot in a corporate org chart. To find all employees K badge-swipes from Alice, the bot can go to subordinates, up to the boss, or side-arm into cousin departments. In binary tree land, we’re making a graph by giving every node a clue about its parent. BFS lets you branch out from your starting node and find who’s exactly K handshakes away—both above and below the waterline.

• Step 1: Use DFS to slap parent links onto every node.
• Step 2: Fire up BFS from your target, hopping left, right, and upward, but never revisiting a node (we’re not that lost).
• Step 3: When you’ve gone K edges, those are your chosen ones.

🛠️ PseudoCode

• Map parents:
  

  void markParents(TreeNode node, Map<TreeNode, TreeNode> parent) {
    if (node.left != null) { parent.put(node.left, node); markParents(node.left, parent); }
    if (node.right != null) { parent.put(node.right, node); markParents(node.right, parent); }
  }
  

  For daytime navigation, because going up is half the job.
• BFS outward from target:
  

  // Queue up the target, track visited
  // At each layer, step out to left, right, parent
  // When steps == K, gather the lucky queue members
  

  It’s like Dijkstra, but your commute is only K stops.
• Edge Case Parade: Target node only (K=0)? Return instantly. K too large? Empty list—don’t invent ghost nodes.
• Take the win: Hand the interviewer your elegant list, resist the urge to mic-drop.

💻 The Code

// TreeNode definition as always
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    markParents(root, parent);
     Queue<TreeNode> queue = new LinkedList<>();
    Set<TreeNode> visited = new HashSet<>();
    queue.offer(target);
    visited.add(target);
    int dist = 0;
     while (!queue.isEmpty()) {
        if (dist == K) break;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            for (TreeNode neighbor : Arrays.asList(node.left, node.right, parent.get(node))) {
                if (neighbor != null && !visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        dist++;
    }
    List<Integer> answer = new ArrayList<>();
    while (!queue.isEmpty()) answer.add(queue.poll().val);
    return answer;
}
 private void markParents(TreeNode node, Map<TreeNode, TreeNode> parent) {
    if (node.left != null) {
        parent.put(node.left, node);
        markParents(node.left, parent);
    }
    if (node.right != null) {
        parent.put(node.right, node);
        markParents(node.right, parent);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No parent mapping = no way up. Don’t let this be your legacy bug.
• K == 0? Why even
  pretend to BFS, hand back the darn target in a list.
• K > tree height? Relax, empty list—don’t hallucinate nodes that aren’t there.
• Distinct nodes, not values. Trees love duplicate values—don’t trust them.
• Time/space: O(N), unless you joylessly break the visited rule and loop forever. Enjoy your infinite recursion stack—mine prints call traces on receipt paper.

🧠 Interviewer Brain-Tattoo

If you treat a tree like a strict hierarchy, you’ll miss the party upstairs. Sometimes, the cool kids are just K flights—and a sideways glance—away.