We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All The Lonely Nodes

Number: 1609

Difficulty: Easy

Paid? Yes

Companies: Microsoft

Problem Description

In a binary tree, a lonely node is defined as a node that is the only child of its parent. The root is not considered lonely because it does not have a parent. Given the root of the tree, return an array of all lonely node values in any order.

Key Insights

  • Traverse the tree using either a DFS (recursive) or BFS (iterative) approach.
  • At each node, check if it has exactly one child.
  • If a node has only one non-null child, that child is lonely and should be added to the result list.
  • Continue traversing until all nodes in the tree are processed.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of nodes in the tree, since each node is visited once. Space Complexity: O(h), where h is the height of the tree. In the worst-case (skewed tree) this becomes O(n).

Solution

We perform a depth-first search (DFS) on the tree. For each node, we check if it has exactly one child. If so, we add that child’s value to our result list. The recursion continues for both children of the current node. The root is ignored because it has no parent. This approach ensures an efficient and straightforward solution.

Code Solutions

# 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

def getLonelyNodes(root):
    # List to hold the values of lonely nodes
    lonely_nodes = []
    
    # Helper function to perform DFS traversal
    def dfs(node):
        if not node:
            return
        # Check if the current node has only one child
        if node.left is None and node.right is not None:
            lonely_nodes.append(node.right.val)
        if node.left is not None and node.right is None:
            lonely_nodes.append(node.left.val)
        # Recursive calls for left and right children
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return lonely_nodes

# Example usage:
# root = TreeNode(1, TreeNode(2, None, TreeNode(4)), TreeNode(3))
# print(getLonelyNodes(root))
← Back to All Questions