Problem Description

A lonely node in a binary tree is defined as a node that is the only child of its parent node - meaning its parent has exactly one child (either left or right, but not both). The root node can never be lonely since it has no parent.

Given the root of a binary tree, you need to find all lonely nodes in the tree and return their values in an array. The values can be returned in any order.

For example, if a parent node has only a left child, that left child is lonely. Similarly, if a parent node has only a right child, that right child is lonely. Nodes that have a sibling (their parent has both left and right children) are not lonely.

The solution uses a depth-first search (DFS) approach to traverse the tree. During traversal, it checks each node to see if it has exactly one child. If a node has only one child, that child's value is added to the result array. The key insight is to check from the parent's perspective - when at a parent node, we check if it has only one child and mark that child as lonely.

The condition root.left == root.right in the code is a clever way to check if both children are None (making it a leaf node) since None == None evaluates to True. The function then checks if either the left or right child is missing (but not both), and adds the existing child's value to the answer array before recursively exploring the subtree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this is a binary tree problem, a tree is a special type of graph (specifically, a connected acyclic graph). Binary trees have nodes and edges connecting parent nodes to child nodes.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to traverse from the root to find lonely nodes.

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem. This makes perfect sense because:

1. We need to traverse the entire tree to find all lonely nodes
2. DFS allows us to explore each path from root to leaves systematically
3. At each parent node, we can check if it has exactly one child (making that child lonely)
4. The recursive nature of DFS naturally fits the recursive structure of trees

The DFS approach lets us visit each node exactly once, check if its children are lonely, and collect all lonely node values in our answer array. This gives us an efficient O(n) time complexity solution where n is the number of nodes in the tree.

Intuition

The key insight is to think about lonely nodes from the parent's perspective rather than the node's own perspective. A node becomes lonely when its parent has exactly one child.

When we traverse the tree, at each parent node we can easily check: does this node have only a left child? Or only a right child? If either condition is true, that single child is lonely.

This naturally leads to a DFS traversal where we:

1. Visit each node in the tree
2. Check if it has exactly one child (either left OR right, but not both)
3. If so, add that child's value to our result

The clever part of the solution is the condition root.left == root.right. This checks if both children are None (making it a leaf node), since None == None evaluates to True. Leaf nodes can't have lonely children, so we return early.

Why DFS? Because we need to examine every parent-child relationship in the tree. DFS lets us systematically visit every node and check its children. The recursive nature of DFS perfectly matches the recursive structure of the tree - we check the current node's children for loneliness, then recursively do the same for each subtree.

The algorithm flows naturally: start at the root, check if any of its children are lonely, then recursively apply the same logic to the left and right subtrees. This ensures we find all lonely nodes throughout the entire tree.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a DFS traversal using a recursive helper function. Let's walk through the implementation step by step:

Data Structure: We use a list ans to collect all lonely node values as we traverse the tree.

Main Algorithm - DFS Function:

The dfs function performs the following steps at each node:

1. Base Case Check: if root is None or root.left == root.right:

   • If the current node is None, there's nothing to process
   • If root.left == root.right, both children are None (since None == None is True), meaning this is a leaf node with no children to be lonely

2. Check for Lonely Left Child: if root.right is None:

   • If the right child is None but we haven't returned (meaning left child exists), then the left child is lonely
   • Add root.left.val to the answer array

3. Check for Lonely Right Child: if root.left is None:

   • If the left child is None but we haven't returned (meaning right child exists), then the right child is lonely
   • Add root.right.val to the answer array

4. Recursive Traversal:

   • Call dfs(root.left) to process the left subtree
   • Call dfs(root.right) to process the right subtree

Execution Flow:

• Initialize an empty list ans to store results
• Start DFS from the root node
• The function recursively visits every node in the tree
• At each parent node, it identifies and records lonely children
• Return the collected list of lonely node values

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through a concrete example to understand how the solution identifies lonely nodes.

Consider this binary tree:

        1
       / \
      2   3
       \
        4

Step-by-step DFS traversal:

1. Start at root (1):

   • Check if node 1 is None or a leaf? No (it has children)
   • Is right child (3) None? No
   • Is left child (2) None? No
   • Both children exist, so neither is lonely
   • Recursively call dfs(2) and dfs(3)

2. Visit left child (2):

   • Check if node 2 is None or a leaf? No (it has a right child)
   • Is right child (4) None? No
   • Is left child None? Yes!
   • Since only the right child exists, node 4 is lonely
   • Add 4 to answer: ans = [4]
   • Recursively call dfs(None) and dfs(4)

3. Visit None (left of 2):

   • Base case: return immediately

4. Visit node 4:

   • Check if node 4 is None or a leaf? Yes (leaf node)
   • root.left == root.right → None == None → True
   • Return immediately (leaf nodes have no children to be lonely)

5. Back to root, visit right child (3):

   • Check if node 3 is None or a leaf? Yes (leaf node)
   • root.left == root.right → None == None → True
   • Return immediately

Final Result: ans = [4]

Node 4 is the only lonely node because it's the only child of its parent (node 2). Nodes 2 and 3 are not lonely because they both have a sibling (node 1 has two children).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses depth-first search (DFS) to traverse the binary tree. Each node in the tree is visited exactly once. At each node, we perform constant time operations:

• Checking if the node is None or if both children are equal (root.left == root.right)
• Checking if either left or right child is None and appending to the result list if needed
• Making recursive calls to left and right children

Since we visit each of the n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of two components:

1. Recursion call stack: In the worst case (a skewed tree), the recursion depth can be O(n). In the best case (a balanced tree), it would be O(log n).
2. Result list (ans): In the worst case, almost all nodes could be lonely nodes (except the root and leaf nodes), so the result list could contain up to O(n) elements.

Taking the worst case scenario for both components, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Checking Node's Own Status Instead of Children's Status

A frequent mistake is trying to determine if the current node itself is lonely, rather than checking if its children are lonely. Remember that we need to check from the parent's perspective.

Incorrect approach:

def dfs(node, parent):
    if node is None:
        return
  
    # Wrong: Checking if current node is lonely
    if parent and ((parent.left == node and parent.right is None) or 
                   (parent.right == node and parent.left is None)):
        result.append(node.val)
  
    dfs(node.left, node)
    dfs(node.right, node)

Correct approach:

def dfs(node):
    if node is None or (node.left is None and node.right is None):
        return
  
    # Correct: Checking if children are lonely
    if node.left is None and node.right is not None:
        result.append(node.right.val)
    if node.right is None and node.left is not None:
        result.append(node.left.val)
  
    dfs(node.left)
    dfs(node.right)

2. Forgetting to Handle the Case Where Both Children Exist

When both children exist, neither is lonely. Some implementations mistakenly add both children when they both exist.

Incorrect:

def dfs(node):
    if node is None:
        return
  
    # Wrong: This would add children even when both exist
    if node.left:
        result.append(node.left.val)
    if node.right:
        result.append(node.right.val)

3. Not Properly Handling Leaf Nodes

Leaf nodes have no children, so they cannot have lonely children. Failing to skip leaf nodes can lead to null pointer exceptions.

Problematic code:

def dfs(node):
    if node is None:
        return
  
    # Dangerous: Not checking if children exist before accessing them
    if node.right is None:
        result.append(node.left.val)  # This could fail if node.left is also None

Safe implementation:

def dfs(node):
    if node is None or (node.left is None and node.right is None):
        return  # Properly skip leaf nodes
  
    if node.right is None:
        result.append(node.left.val)  # Safe because we know at least one child exists

4. Using root.left == root.right Without Understanding Its Purpose

While root.left == root.right is a clever way to check if both children are None, using it without understanding can lead to confusion or bugs if the tree node implementation changes.

More explicit alternative:

# Clearer for readability
if node is None or (node.left is None and node.right is None):
    return

This makes the intent more obvious and is less prone to misunderstanding during code maintenance.