Find All The Lonely Nodes

class Solution {
public:
    vector<int> findLonelyNodes(TreeNode* root) {
        vector<int> lonelyNodes;
        
        queue<pair<TreeNode*, bool>> nodeQueue;
        nodeQueue.push({root, false});

        while (!nodeQueue.empty()) {
            auto nodeInfo = nodeQueue.front();
            nodeQueue.pop();
            
            TreeNode* node = nodeInfo.first;
            bool isLonely = nodeInfo.second;

            if (isLonely) {
                lonelyNodes.push_back(node->val);
            }
            
            if (node->right) {
                nodeQueue.push({node->right, node->left == nullptr});
            }

            if (node->left) {
                nodeQueue.push({node->left, node->right == nullptr});
            }
        }
        
        return lonelyNodes;
    }
};

This solution addresses the problem of identifying all the lonely nodes in a binary tree using C++. Here, a lonely node is defined as a non-root node that is the only child of its parent. The provided C++ function leverages a breadth-first search (BFS) approach to traverse the binary tree and identify these nodes.

The function findLonelyNodes accepts the root of the binary tree as an input and returns a vector containing the values of all lonely nodes. A queue is utilized to perform the BFS. Each element in the queue is a pair consisting of a pointer to a node (TreeNode*) and a boolean indicating whether this node is considered lonely. The initial state begins with the root node which is inherently not lonely.

As the tree is traversed level by level:

• The current node's information is examined. If it is marked as lonely (i.e., the boolean in the pair is true), its value is added to the result vector of lonely nodes.
• If the current node has a right child, this child is added to the queue and marked lonely only if there is no left child for the current node.
• Similarly, if the current node has a left child, this child is added to the queue and marked lonely only if there is no right child for the current node.

This approach ensures that all nodes are checked for loneliness based on their sibling status and collected accordingly. The function ultimately returns a vector containing the values of all identified lonely nodes, providing an efficient solution to the problem statement.

class Solution {
    public List<Integer> findLonelyNodes(TreeNode root) {
        List<Integer> lonelyNodes = new ArrayList<>();
        
        Queue<Pair<TreeNode, Boolean>> queue = new LinkedList<>();
        queue.add(new Pair(root, false));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Boolean> front = queue.remove();
            
            TreeNode node = front.getKey();
            Boolean isSingleChild = front.getValue();

            if (isSingleChild) {
                lonelyNodes.add(node.val);
            }
            
            if (node.right != null) {
                queue.add(new Pair(node.right, node.left == null));
            }

            if (node.left != null) {
                queue.add(new Pair(node.left, node.right == null));
            }
        }
        
        return lonelyNodes;
    }
}

The Java program provided defines a method findLonelyNodes that identifies "lonely" nodes in a binary tree. A "lonely" node is defined as one that is the only child of its parent. The solution employs a Breadth-First Search (BFS) algorithm using a queue to traverse the tree iteratively. Here's how the solution works:

• Initialize a list lonelyNodes to store the values of the lonely nodes.
• Utilize a Queue wherein each element is a Pair consisting of a TreeNode and a Boolean. The TreeNode represents the current node being explored, and the Boolean signifies if it is a single child.
• Begin with the root node. Enqueue it paired with false since the root isn't inherently lonely.
• Use a loop to iterate as long as the queue isn't empty.
  • Dequeue an element and check if it's marked as a single child (isSingleChild). If true, add the node's value to the list of lonely nodes.
  • Check each child of the current node:
    • If the node has a right child, enqueue it. The child is lonely if there's no left sibling, i.e., if node.left == null.
    • If the node has a left child, enqueue it, determining its loneliness by the absence of its right sibling (node.right == null).
• Continue this process until the queue is empty.
• Finally, return the list of lonely nodes.

This method effectively collects all lonely nodes in the tree by checking siblings during traversal. Using BFS ensures that each node is visited in the shortest path order from the root, which optimizes the process for larger trees. The use of Pair helps keep track of whether each node being evaluated is a lonely node, resulting in a clean and efficient solution to determine loneliness based on the presence of sibling nodes.