LeetCode 1469 - Find All The Lonely Nodes
This problem asks us to traverse a binary tree and identify every node that is considered "lonely". A node is lonely if
Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Solution
Problem Understanding
This problem asks us to traverse a binary tree and identify every node that is considered "lonely". A node is lonely if it is the only child of its parent. In other words, if a parent node has exactly one child, that child is lonely.
The input is the root of a binary tree. Each node may have:
- a left child,
- a right child,
- both children,
- or no children.
The output should be a list containing the values of all lonely nodes in any order.
The important detail is that loneliness depends entirely on the parent node. A node itself does not determine whether it is lonely. Instead, we examine the parent:
- if the parent has only a left child, then the left child is lonely,
- if the parent has only a right child, then the right child is lonely,
- if the parent has both children, neither child is lonely.
The root node is never lonely because it does not have a parent.
The constraints tell us that the tree contains at most 1000 nodes. This is small enough that a full traversal of the tree is completely acceptable. Since every node may need to be examined, an O(n) solution is ideal and straightforward.
Several edge cases are important:
- A tree with only one node should return an empty list because the root cannot be lonely.
- A completely balanced tree may contain no lonely nodes.
- A tree shaped like a linked list will make every non-root node lonely.
- Nodes with exactly one child must be handled carefully so we do not accidentally miss them or count the wrong node.
Approaches
Brute Force Approach
A brute-force style solution would examine every node and repeatedly determine whether each node is lonely by checking its parent relationship. One way to do this is:
- Traverse the tree and store parent references in a map.
- Traverse again and determine whether each node is the only child of its parent.
This works because every node eventually gets paired with its parent, allowing us to determine whether it has a sibling.
However, this approach performs unnecessary extra work. We do not actually need a second traversal or a parent map because the parent already knows whether it has one child or two at the moment we visit it.
Optimal Approach
The key observation is that loneliness can be determined immediately while traversing the tree.
When visiting a node:
- if it has a left child but no right child, the left child is lonely,
- if it has a right child but no left child, the right child is lonely.
This means a single Depth-First Search traversal is enough. As we recursively process each node, we directly append lonely child values to the result list.
This eliminates the need for extra bookkeeping structures such as parent maps.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Uses extra parent mapping and multiple traversals |
| Optimal | O(n) | O(h) | Single DFS traversal, where h is tree height |
Algorithm Walkthrough
- Create an empty list called
lonely_nodesto store the answer. - Start a Depth-First Search from the root node.
- For each node, check whether it has exactly one child.
- If the node has a left child but no right child, append the left child's value to the result list.
- If the node has a right child but no left child, append the right child's value to the result list.
- Recursively continue traversal on the left subtree.
- Recursively continue traversal on the right subtree.
- Once the traversal finishes, return the collected result list.
The DFS traversal is a natural fit because every node must be visited exactly once, and the recursive structure of the tree maps directly onto recursive DFS.
Why it works
The algorithm works because every lonely node is uniquely determined by its parent. During traversal, every parent node is examined exactly once. At that moment, we can determine whether one of its children lacks a sibling. Since every edge in the tree is checked exactly once, all lonely nodes are identified and none are missed.
Python Solution
# 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: Optional[TreeNode]) -> List[int]:
lonely_nodes = []
def dfs(node):
if not node:
return
if node.left and not node.right:
lonely_nodes.append(node.left.val)
if node.right and not node.left:
lonely_nodes.append(node.right.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return lonely_nodes
The implementation begins by creating the lonely_nodes list that will store all lonely node values.
The nested dfs function performs recursive traversal. The first condition handles the base case. If the current node is None, recursion stops immediately.
The next two conditions check whether the current node has exactly one child:
node.left and not node.rightnode.right and not node.left
Whenever one of these conditions is true, the corresponding child is lonely, so its value is appended to the result list.
Finally, recursion continues into both subtrees so every node in the tree is processed.
After traversal completes, the accumulated list is returned.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getLonelyNodes(root *TreeNode) []int {
result := []int{}
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
if node.Left != nil && node.Right == nil {
result = append(result, node.Left.Val)
}
if node.Right != nil && node.Left == nil {
result = append(result, node.Right.Val)
}
dfs(node.Left)
dfs(node.Right)
}
dfs(root)
return result
}
The Go implementation follows the same logic as the Python version. The main difference is the use of slices instead of Python lists and explicit nil checks instead of Python truthiness.
The recursive DFS function is declared using a function variable so it can recursively call itself.
Go slices dynamically grow as values are appended, making them a natural choice for collecting lonely node values.
Integer overflow is not a concern because node values are only stored and returned, not used in arithmetic operations.
Worked Examples
Example 1
Input:
1
/ \
2 3
\
4
Expected Output:
[4]
Traversal process:
| Current Node | Left Child | Right Child | Lonely Node Added | Result |
|---|---|---|---|---|
| 1 | 2 | 3 | None | [] |
| 2 | None | 4 | 4 | [4] |
| 4 | None | None | None | [4] |
| 3 | None | None | None | [4] |
Final result:
[4]
Example 2
Input:
7
/ \
1 4
/ / \
6 5 3
\
2
Expected Output:
[6,2]
Traversal process:
| Current Node | Left Child | Right Child | Lonely Node Added | Result |
|---|---|---|---|---|
| 7 | 1 | 4 | None | [] |
| 1 | 6 | None | 6 | [6] |
| 6 | None | None | None | [6] |
| 4 | 5 | 3 | None | [6] |
| 5 | None | None | None | [6] |
| 3 | None | 2 | 2 | [6,2] |
| 2 | None | None | None | [6,2] |
Final result:
[6,2]
Example 3
Input:
11
/ \
99 88
/ \
77 66
/ \
55 44
/ \
33 22
Expected Output:
[77,55,33,66,44,22]
Traversal process:
| Current Node | Lonely Child | Result |
|---|---|---|
| 11 | None | [] |
| 99 | 77 | [77] |
| 77 | 55 | [77,55] |
| 55 | 33 | [77,55,33] |
| 88 | 66 | [77,55,33,66] |
| 66 | 44 | [77,55,33,66,44] |
| 44 | 22 | [77,55,33,66,44,22] |
Final result:
[77,55,33,66,44,22]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is visited exactly once |
| Space | O(h) | Recursive call stack stores up to tree height |
The algorithm performs a single DFS traversal across the tree. Since each node is processed one time, the total time complexity is linear in the number of nodes.
The space complexity comes from recursion depth. In a balanced tree, the height is approximately log n. In the worst case, such as a completely skewed tree, the height becomes n.
Test Cases
# Helper TreeNode definition
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):
result = []
def dfs(node):
if not node:
return
if node.left and not node.right:
result.append(node.left.val)
if node.right and not node.left:
result.append(node.right.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return result
solution = Solution()
# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.right = TreeNode(4)
assert solution.getLonelyNodes(root1) == [4] # single lonely node
# Example 2
root2 = TreeNode(7)
root2.left = TreeNode(1)
root2.right = TreeNode(4)
root2.left.left = TreeNode(6)
root2.right.left = TreeNode(5)
root2.right.right = TreeNode(3)
root2.right.right.right = TreeNode(2)
assert sorted(solution.getLonelyNodes(root2)) == [2, 6] # multiple lonely nodes
# Example 3
root3 = TreeNode(11)
root3.left = TreeNode(99)
root3.right = TreeNode(88)
root3.left.left = TreeNode(77)
root3.left.left.left = TreeNode(55)
root3.left.left.left.left = TreeNode(33)
root3.right.right = TreeNode(66)
root3.right.right.right = TreeNode(44)
root3.right.right.right.right = TreeNode(22)
assert sorted(solution.getLonelyNodes(root3)) == [22, 33, 44, 55, 66, 77] # skewed structure
# Single node tree
root4 = TreeNode(1)
assert solution.getLonelyNodes(root4) == [] # root is never lonely
# Perfect binary tree
root5 = TreeNode(1)
root5.left = TreeNode(2)
root5.right = TreeNode(3)
root5.left.left = TreeNode(4)
root5.left.right = TreeNode(5)
root5.right.left = TreeNode(6)
root5.right.right = TreeNode(7)
assert solution.getLonelyNodes(root5) == [] # no lonely nodes
# Left-skewed tree
root6 = TreeNode(1)
root6.left = TreeNode(2)
root6.left.left = TreeNode(3)
root6.left.left.left = TreeNode(4)
assert solution.getLonelyNodes(root6) == [2, 3, 4] # every non-root node is lonely
# Right-skewed tree
root7 = TreeNode(1)
root7.right = TreeNode(2)
root7.right.right = TreeNode(3)
assert solution.getLonelyNodes(root7) == [2, 3] # chain on the right side
| Test | Why |
|---|---|
| Example 1 | Verifies detection of a single lonely node |
| Example 2 | Verifies multiple lonely nodes in different subtrees |
| Example 3 | Verifies deep skewed structures |
| Single node tree | Ensures root is not incorrectly marked lonely |
| Perfect binary tree | Ensures nodes with siblings are excluded |
| Left-skewed tree | Verifies repeated lonely relationships |
| Right-skewed tree | Verifies right-child-only handling |
Edge Cases
Single Node Tree
A tree containing only the root node is an important edge case because the root has no parent and therefore cannot be lonely. A buggy implementation might accidentally include it if it only checks child counts without considering parent existence. The implementation handles this naturally because loneliness is determined only while examining parent nodes.
Completely Balanced Tree
In a perfect binary tree, every internal node has exactly two children. Therefore, no node is lonely. This case verifies that the algorithm does not mistakenly include nodes simply because they are leaves. The implementation correctly checks for exactly one child before appending anything to the result.
Highly Skewed Tree
A tree shaped like a linked list causes every non-root node to be lonely. This is a useful stress case because recursion depth reaches its maximum possible value. The algorithm still works correctly because each parent node independently identifies its single child as lonely.
Missing Left or Right Child
Some implementations accidentally handle only left-child cases or only right-child cases. The problem requires detecting loneliness regardless of direction. The solution explicitly checks both:
- left child exists and right child does not,
- right child exists and left child does not.
This guarantees correctness for asymmetric trees.