Find All The Lonely Nodes - Solution & Explanation

Problem Overview: Given the root of a binary tree, return all lonely nodes. A node is considered lonely if its parent has exactly one child. In other words, if a parent has only a left child or only a right child, that child is lonely and should be added to the result.

Approach 1: Depth-First Search (DFS) Traversal (O(n) time, O(h) space)

The most direct solution is a recursive DFS over the binary tree. At each node, check whether it has exactly one child. If node.left exists and node.right is null, the left child is lonely. If node.right exists and node.left is null, the right child is lonely. Add the lonely child's value to the result and continue traversing both subtrees.

This approach works because every node is visited exactly once, and the lonely condition depends only on the immediate parent. DFS naturally fits tree problems since recursion mirrors the tree structure. The traversal can be implemented with preorder, inorder, or postorder—any order works since the decision only depends on the current node’s children. Time complexity is O(n) because each node is processed once. Space complexity is O(h), where h is the tree height due to the recursion stack.

DFS is the most common approach for problems involving structural checks in a binary tree. Interviewers often expect this pattern: visit a node, inspect its children, then recurse. If you're comfortable with depth-first search, the implementation is only a few lines.

Approach 2: Breadth-First Search (BFS) with Queue (O(n) time, O(w) space)

The same logic can be implemented using level-order traversal. Use a queue to process nodes layer by layer. For each dequeued node, check whether exactly one child exists. If so, record that child’s value and push it into the queue for further processing.

BFS visits every node once, so the time complexity remains O(n). The space complexity becomes O(w), where w is the maximum width of the tree, because the queue may hold an entire level at once. This approach is useful when you already need level-order traversal or when recursion depth could become large. It relies on the same core idea used in many breadth-first search tree problems.

Recommended for interviews: The DFS approach is usually preferred. It’s concise, easy to reason about, and uses minimal additional data structures. A BFS solution also works and demonstrates familiarity with level-order traversal, but recursive DFS tends to be the cleanest implementation. Showing both approaches signals strong understanding of tree traversal patterns.