Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def getLonelyNodes(self, root: TreeNode) -> List[int]:
        lonely = []
        def dfs(node):
            if not node:
                return
            if node.left and not node.right:
                lonely.append(node.left.val)
            if node.right and not node.left:
                lonely.append(node.right.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return lonely
    

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> lonely;
        dfs(root, lonely);
        return lonely;
    }
    void dfs(TreeNode* node, vector<int>& lonely) {
        if (!node) return;
        if (node->left && !node->right)
            lonely.push_back(node->left->val);
        if (node->right && !node->left)
            lonely.push_back(node->right->val);
        dfs(node->left, lonely);
        dfs(node->right, lonely);
    }
};
    

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> lonely = new ArrayList<>();
        dfs(root, lonely);
        return lonely;
    }
    private void dfs(TreeNode node, List<Integer> lonely) {
        if (node == null) return;
        if (node.left != null && node.right == null)
            lonely.add(node.left.val);
        if (node.right != null && node.left == null)
            lonely.add(node.right.val);
        dfs(node.left, lonely);
        dfs(node.right, lonely);
    }
}
    

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var getLonelyNodes = function(root) {
    const lonely = [];
    function dfs(node) {
        if (!node) return;
        if (node.left && !node.right) lonely.push(node.left.val);
        if (node.right && !node.left) lonely.push(node.right.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return lonely;
};
    

Problem Description

Given the root of a binary tree, you are asked to find all "lonely" nodes in the tree. A node is called lonely if and only if it is the only child of its parent node. In other words, for a parent node, if it has exactly one child (either left or right, but not both), that child is lonely.

Your task is to return a list of values of all such lonely nodes in any order. The input is provided as a root node of a binary tree. The structure of the tree and the values of the nodes are arbitrary. There is no guarantee of a unique solution, and you should not reuse elements.

Thought Process

The first step is to understand what it means for a node to be lonely: it must be the only child of its parent. That means, for every parent node, we need to check if it has exactly one child. If it does, the child is lonely and should be included in our result.

A brute-force approach would be to traverse every node in the tree and, for each node, check its children. If a node has only one child, add that child to the result list. We can accomplish this using either a depth-first search (DFS) or breadth-first search (BFS).

There is no need for complex data structures or optimizations, since each node is visited only once and the check is straightforward. The key realization is that the "lonely" status of a node depends solely on its parent, not on the node itself.

Solution Approach

• Step 1: Tree Traversal
  • We use a recursive DFS (depth-first search) to visit every node in the tree.
• Step 2: Lonely Node Check
  • At each node, check if it has exactly one child (left or right, but not both).
  • If only the left child exists, add its value to the result list.
  • If only the right child exists, add its value to the result list.
• Step 3: Recursion
  • Recursively apply the same check to both the left and right children.
• Step 4: Collect Results
  • Maintain a list to collect the values of all lonely nodes found during traversal.
  • Return this list at the end.

This approach ensures that every node is visited exactly once, and the check for loneliness is performed efficiently at each visit.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
       \
        4
         \
          5
  

• Start at root 1: has two children (2 and 3), so no lonely nodes yet.
• Move to node 2: only has a right child (4), so 4 is lonely.
• Move to node 3: no children, nothing to add.
• Move to node 4: only has a right child (5), so 5 is lonely.
• Node 5: no children, nothing to add.

The result is [4, 5] (order may vary).

Time and Space Complexity

• Brute-force Approach:
  • Still requires visiting every node once: O(N), where N is the number of nodes.
  • Space complexity is O(H) for the recursion stack, where H is the height of the tree.
• Optimized Approach:
  • Our recursive DFS is already optimal: O(N) time, O(H) space.
  • Only one pass through the tree, and no extra data structures are needed beyond the result list.

Summary

To find all lonely nodes in a binary tree, we traverse the tree using DFS and, at each step, check if a node has exactly one child. If so, we add that child to our result list. This approach is efficient, elegant, and leverages the recursive nature of trees. The solution is both simple and optimal, making it easy to understand and implement.