Find All The Lonely Nodes

You can traverse the binary tree and find the lonely nodes by checking the children of each node. If a node has only one child, that child is considered a lonely node.

Here’s the code to find lonely nodes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
        lonely_nodes = []  # List to store values of lonely nodes

        # Helper function to perform in-order traversal
        def traverse(node):
            if node is None:
                return

            # Check the left child
            if node.left is not None and node.right is None:
                lonely_nodes.append(node.left.val)
            # Check the right child
            if node.right is not None and node.left is None:
                lonely_nodes.append(node.right.val)

            # Traverse left subtree
            traverse(node.left)
            # Traverse right subtree
            traverse(node.right)

        # Start traversal from the root
        traverse(root)
        return lonely_nodes

The function traverse performs an in-order traversal of the tree and checks if a node has exactly one child. If it does, that child is added to the lonely_nodes list. Finally, the function returns the list of lonely nodes.

The time complexity of this solution is O(n), and the space complexity is also O(n), where n is the number of nodes in the binary tree.