Domain 1EasyCORE

Find All The Lonely Nodes

The problem requires identifying "lonely nodes" in a binary tree. A lonely node is defined as a node that has only one child (i.e., it is an only child of its parent). The root node is never considered lonely because it does not have a parent.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search

1469. Find All The Lonely Nodes

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search
FAANG asked: 0
Acceptance rate: 80.5%


Problem Breakdown

The problem requires identifying “lonely nodes” in a binary tree. A lonely node is defined as a node that has only one child (i.e., it is an only child of its parent). The root node is never considered lonely because it does not have a parent.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • An array containing the values of all lonely nodes in the tree. The order of the elements in the array does not matter.

Implicit Constraints or Tricky Edge Cases:

  • The tree can be empty (i.e., root is None). In this case, the output should be an empty list.
  • The tree can have only one node (the root), which means there are no lonely nodes.
  • Nodes with values between 1 and (10^6).

Intuition

A brute-force approach would involve traversing the entire tree and checking each node to see if it has exactly one child. If a node is found to be lonely, its value is added to the result list. This approach would have a time complexity of (O(n)), where (n) is the number of nodes in the tree, which is acceptable given the problem constraints.

However, the key insight here is that we can optimize this process by using a depth-first search (DFS) traversal. During the traversal, we can directly check if a node has only one child and add it to the result list immediately. This approach maintains the same time complexity but simplifies the logic by leveraging the properties of DFS.

Approach

We will use a recursive DFS approach to traverse the binary tree. The algorithm works as follows:

  1. Base Case: If the current node is None, return.
  2. Check for Lonely Node: If the current node has only one child (either left or right), add that child’s value to the result list.
  3. Recursive Calls: Recursively call the function on the left and right children of the current node.

This approach ensures that we visit each node exactly once, making it efficient in terms of both time and space.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the number of nodes in the tree. This is because we visit each node exactly once.
  • Space Complexity: (O(h)), where (h) is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), the space complexity can be (O(n)).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def getLonelyNodes(root: TreeNode) -> list[int]:
    lonely_nodes = []
    
    def dfs(node: TreeNode):
        if not node:
            return
        
        # Check if the current node is lonely
        if (node.left and not node.right) or (node.right and not node.left):
            lonely_nodes.append(node.left.val if node.left else node.right.val)
        
        # Recur for left and right children
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return lonely_nodes

Edge Cases Handled

  • Empty Tree: If the input tree is empty (root is None), the function will return an empty list immediately.
  • Single Node Tree: If the tree contains only one node (the root), there are no lonely nodes, and the function will return an empty list.
  • Nodes with Only One Child: The function correctly identifies and adds these nodes to the result list.