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.,
rootisNone). 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:
- Base Case: If the current node is
None, return. - 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.
- 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 (
rootisNone), 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.