Find All The Lonely Nodes

#378 Most AskedEasy

Find All The Lonely Nodes #378 Most Asked

Easy

Microsoft

9 views

Topics:

TreesRecursion

You are given the root of a binary tree. A node is considered lonely if it is the only child of its parent.

Return an array containing the values of all lonely nodes in the tree. Return the list in any order.

Example 1:

Input: root = [1,2,3,null,4]
Output: [4]
Explanation: The node with value 2 is the only child of the node with value 1.The node with value 4 is the only child of the node with value 2. Hence the lonely nodes are [4].

Example 2:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: The node with value 1 is the only child of the node with value 7.The node with value 6 is the only child of the node with value 1.The node with value 5 is the only child of the node with value 4.The node with value 2 is the only child of the node with value 3. Hence the lonely nodes are [6, 2].

Example 3:

Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]
Output: [77,55,44,33,22]
Explanation: Nodes with values 99 and 88 have no siblings.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
1 <= Node.val <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, and if so, what should I return?
What is the range of values for the nodes in the tree? Can they be negative?
If a node has both a left and a right child, but one of them has a value that is equal to the parent, is that child considered lonely?
Is the order of the lonely node values in the returned list important?
Can the same value appear as a lonely node multiple times, and should I include it multiple times in the output if so?

Brute Force Solution

Approach

We're trying to find all the 'lonely' nodes in a family tree. The brute force way to do this is to look at every single person in the tree and check their siblings. If they don't have a sibling, they're lonely.

Here's how the algorithm would work step-by-step:

Start by looking at the very first person in the tree.
Check if this person has a brother or sister.
If they don't have a sibling, mark them as lonely.
Now, move on to the next person in the tree.
Repeat the process of checking if they have a sibling.
If they don't, mark them as lonely.
Keep doing this for every single person in the entire tree.
Once you've checked everyone, you'll have a list of all the lonely people.

Code Implementation

def find_lonely_nodes_brute_force(root):
    lonely_nodes = []

    def traverse(node):
        if not node:
            return

        # Check if current node has exactly one child
        if (node.left and not node.right) or (not node.left and node.right):

            # Add the single child to the lonely_nodes list
            if node.left:
                lonely_nodes.append(node.left.val)
            else:
                lonely_nodes.append(node.right.val)

        # Recursively traverse left and right subtrees
        traverse(node.left)
        traverse(node.right)

    traverse(root)
    return lonely_nodes

Big(O) Analysis

Time Complexity

O(n) – The proposed brute-force approach iterates through each node in the binary tree, which represents n nodes. For each node, we check if its sibling exists. In a binary tree, checking for a sibling involves accessing the parent node, a constant time operation O(1). Therefore, we perform a constant-time operation for each of the n nodes in the tree. Thus, the time complexity is O(n * 1), simplifying to O(n).

Space Complexity

O(1) – The provided plain English explanation describes iterating through each node of a tree and checking its siblings. It doesn't explicitly mention any auxiliary data structures being used like lists, hash maps, or queues for storing intermediate results or for traversal. The described process only involves examining individual nodes and their immediate relatives. Therefore, the algorithm described utilizes constant extra space, independent of the input tree size N, where N is the number of nodes.

Optimal Solution

Approach

The goal is to identify nodes in a binary tree that are 'lonely', meaning they have a parent but no sibling. We can efficiently find these lonely nodes by traversing the tree and checking each node's children.

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree, the root node.
For each node, check if it has only one child (either a left child or a right child, but not both).
If a node has only one child, then that child is a lonely node, so remember it.
Continue this process for all nodes in the tree, going down each branch.
Once you've checked all the nodes, you will have found all the lonely nodes.

Code Implementation

def find_lonely_nodes(root):
    lonely_node_values = []

    def traverse_tree(node):
        if not node:
            return

        # Check if the current node has only one child
        if node.left and not node.right:
            lonely_node_values.append(node.left.val)

        if node.right and not node.left:
            # Add the lonely node's value to the list
            lonely_node_values.append(node.right.val)

        traverse_tree(node.left)
        # Recursively check the right subtree for lonely nodes
        traverse_tree(node.right)

    traverse_tree(root)
    return lonely_node_values

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree, visiting each node exactly once to check its children. For each node, it performs a constant amount of work (checking if it has one child). Therefore, the time complexity is directly proportional to the number of nodes in the tree, where n represents the number of nodes.

Space Complexity

O(N) – The algorithm performs a tree traversal which can be implemented using recursion or an iterative approach with a queue or stack. In the worst-case scenario (e.g., a skewed tree), the recursion stack or the queue/stack will hold all N nodes of the tree. Therefore, the auxiliary space required is proportional to the number of nodes in the tree, N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list if the root is null, indicating no lonely nodes exist.
Single Node Tree	Return an empty list because a single node cannot be lonely.
Complete Binary Tree (no lonely nodes)	The algorithm should iterate through the tree and return an empty list if no lonely nodes are found.
Highly Skewed Tree (all nodes on one side)	The traversal should still correctly identify lonely nodes in skewed trees.
Tree with duplicate values	The algorithm should correctly identify lonely nodes regardless of duplicate values; the node's position is what matters, not the value.
Tree with negative, zero, and positive values	The node values should not affect the logic of identifying lonely nodes, which depends solely on the tree structure.
Maximum Tree Depth (potential stack overflow with recursion)	Use an iterative approach (e.g., Breadth-First Search) to avoid stack overflow issues with very deep trees instead of recursive Depth First Search.
Tree with only lonely nodes	The algorithm correctly collects all node values that fulfill the 'lonely node' criterion into the result list.

Null or Empty Tree

How to Handle:

Return an empty list if the root is null, indicating no lonely nodes exist.

Single Node Tree

How to Handle:

Return an empty list because a single node cannot be lonely.

Complete Binary Tree (no lonely nodes)

How to Handle:

The algorithm should iterate through the tree and return an empty list if no lonely nodes are found.

Highly Skewed Tree (all nodes on one side)

How to Handle:

The traversal should still correctly identify lonely nodes in skewed trees.

Tree with duplicate values

How to Handle:

The algorithm should correctly identify lonely nodes regardless of duplicate values; the node's position is what matters, not the value.

Tree with negative, zero, and positive values

How to Handle:

The node values should not affect the logic of identifying lonely nodes, which depends solely on the tree structure.

Maximum Tree Depth (potential stack overflow with recursion)

How to Handle:

Use an iterative approach (e.g., Breadth-First Search) to avoid stack overflow issues with very deep trees instead of recursive Depth First Search.

Tree with only lonely nodes

How to Handle:

The algorithm correctly collects all node values that fulfill the 'lonely node' criterion into the result list.