Find All The Lonely Nodes

Find All The Lonely Nodes

What is this problem about?

The Find All The Lonely Nodes interview question introduces a simple but interesting tree property. In a binary tree, a node is considered "lonely" if it is the only child of its parent. In other words, its parent has exactly one child. Your goal is to traverse the tree and return a list containing the values of all such lonely nodes.

Why is this asked in interviews?

This "Easy" difficulty question is frequently asked by Microsoft to test a candidate's baseline proficiency with tree traversal. It evaluations whether you can correctly identify parent-child relationships and handle null checks. The Binary Tree interview pattern here checks for clarity in recursive logic and the ability to implement a traversal (either BFS or DFS) without overcomplicating the search condition.

Algorithmic pattern used

This problem is solved using Depth-First Search (DFS) or Breadth-First Search (BFS). As you traverse the tree, for every node you visit, you check its children:

1. If the node has a left child but no right child, the left child is lonely.
2. If the node has a right child but no left child, the right child is lonely.
3. If it has both or neither, no nodes are added to the result from this specific parent.

Example explanation

Consider this tree:

    1
   / 
  2   3
   
    4

1. Start at Root(1). It has two children (2 and 3). None are lonely.
2. Move to Node 2. It has only one child: Node 4 (right child).
3. Node 4 is lonely. Add its value to the result.
4. Move to Node 3. It has no children. Result: [4].

Common mistakes candidates make

• Misidentifying the lonely node: Adding the parent instead of the child to the result list.
• Root handling: Trying to check if the root is lonely (it has no parent, so by definition, it cannot be a "only child").
• Redundant checks: Checking if a node has a parent within the recursive call rather than letting the parent check its own children.

Interview preparation tip

For tree problems involving properties of a node relative to its parent, it's often easier to make the decision at the parent node. This allows you to check both children simultaneously and avoid passing extra "parent" state through your recursive function.