1469. Find All The Lonely Nodes

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

In this problem, you are given a binary tree and need to find all the "lonely" nodes within it. A lonely node is defined as a node that is the only child of its parent, meaning it has no sibling. The node, in this context, could be either a left child with no right sibling or a right child with no left sibling. It is important to note that the root of the tree is not considered lonely since it does not have a parent. The goal is to return a list of the values of these lonely nodes. The order of values in the output list is not important.

Flowchart Walkthrough

Let's analyze LeetCode problem 1469, Find All The Lonely Nodes, using the Flowchart. Here's a step-by-step walkthrough based on the flowchart:

Is it a graph?

Yes: In this problem, the binary tree can be considered as a specific form of a graph.

Is it a tree?

Yes: Specifically, the problem involves a binary tree.

DFS

Given that it's a tree, one effective way to traverse and answer problems related to trees is by using Depth-First Search (DFS). DFS is particularly useful in trees to explore each branch to its fullest before moving onto the next branch.

Conclusion: The flowchart directs us to utilize Depth-First Search for efficiently solving problems on trees, like identifying all lonely nodes in this problem.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The solution to this problem uses a classic tree traversal approach using a Depth-First Search (DFS) algorithm. The idea is to traverse the tree starting from the root and check at each node if it has any lonely children. If a node has exactly one child (either left or right), that child is a lonely node, and its value is added to the answer list.

Here’s the intuition behind the DFS approach for this problem:

Start DFS from the root of the tree.
Upon visiting each node, check if the node has only one child.
If the node only has a left child (meaning the right child is None), record the value of the left child.
If the node only has a right child (meaning the left child is None), record the value of the right child.
Recur for both the left and right children of the current node.
Once DFS is complete, the answer list will contain the values of all the lonely nodes.
Return the answer list.

This method ensures that every node is visited, and no lonely nodes are missed. It uses the recursive nature of DFS to backtrack and traverse all paths within the tree efficiently.

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

Solution Approach

The provided Python solution implements a recursive Depth-First Search (DFS) strategy on the binary tree, which is a common approach for solving tree traversal problems.

Here's a step-by-step explanation of how the code works:

A helper function named dfs is defined, which will be invoked on the root node and recursively on each child. The root parameter of this function refers to the current node being visited.
The base case of our recursive function checks for two conditions:
- If the root is None, meaning we have reached a leaf node's child (which doesn't exist), in which case the function returns immediately without doing anything further.
- If both the left and right children of the current node are None, meaning the current node is a leaf, there's no need to proceed further as leaf nodes cannot have lonely nodes.
For each non-null node visited by dfs, the function checks if the node has a single child. This is verified by checking if root.left is None when a right child exists, or root.right is None when a left child exists.
If the node has only one child, the value of that lonely child node (root.right.val or root.left.val) is added to the ans list.
After checking for loneliness, dfs is called recursively on both the left and right children of the current node, if they exist. This allows the function to traverse the whole tree thoroughly.
Before calling the dfs function, an empty list named ans is created. This will be used to collect the values of the lonely nodes that are encountered during the recursion.
The dfs function is called with the root of the binary tree as its argument, starting the traversal.
Once the full tree has been traversed, the ans list is complete, and it is returned as the final result.

The underlying concepts used in this solution include recursive functions, tree traversal, and DFS, which is a fundamental pattern for exploring all nodes of a tree systematically. This specific problem doesn’t require maintaining any additional data structures aside from the ans list that accumulates the result. The simplicity and elegance of recursion make the solution concise and highly readable.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a binary tree with the following structure:

    1
   / \
  2   3
 /   / \
4   5   null
   /
  6

In this tree:

Node 1 is the root and has two children (2 and 3), so it's not lonely.
Node 2 has one child (4), but no right sibling, so it's lonely.
Node 3 has one child missing (right child), so its left child (5) is lonely.
Node 4 is the only child of node 2, and it's also lonely.
Node 5 has a left child (6), but no right sibling, so node 5 is also lonely.

We want to find all the lonely nodes, which in this case are 2, 4, 5, and 6.

Now, following the solution approach:

We define dfs(root), which we'll call on the root node (1 in our example).
We check if root is None. Since 1 has children, it's not None, we proceed. It's also not a leaf, so no base case conditions are met.
We check if node 1 has a single child. It has two, so no nodes are added to the ans list.
We call dfs(2) and dfs(3) recursively.

For node 2:

It's not None, and it's not a leaf.
Check if node 2 has a single child: Node 2 has only one child (4), so we add 4 to ans.
We call dfs(4) recursively.

For node 4:

It is None when checking for its children, so no further actions are taken (leaf node).

For node 3:

It's not None, and it's not a leaf.
Node 3 has one child missing (right child is None), so we add 5 (its left child) to ans.
We call dfs(5).

For node 5:

It's not None, and it's not a leaf.
Node 5 has no right sibling, so we add 6 (its left child) to ans.
We call dfs(6).

For node 6:

All children are None. It's a leaf node, so no further action is taken.

After all recursions complete, we've added all the values of the lonely nodes - 4, 5, and 6 - to the ans list.

We would have just walked through the algorithm to correctly identify nodes 4, 5, and 6 as the lonely nodes in the given tree based on the DFS strategy laid out in the problem's solution approach.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def get_lonely_nodes(self, root: Optional[TreeNode]) -> List[int]:
10        """
11        Perform a depth-first search to find all nodes that have only one child (lonely nodes)
12        """
13
14        # Helper function to perform DFS
15        def dfs(node):
16            # If the node is None or is a leaf node (no children), there's nothing to do
17            if node is None or (node.left is None and node.right is None):
18                return
19          
20            # If the node has a right child but no left child, add the right child's value
21            if node.left is None:
22                lonely_nodes.append(node.right.val)
23          
24            # If the node has a left child but no right child, add the left child's value
25            if node.right is None:
26                lonely_nodes.append(node.left.val)
27          
28            # Recursively apply DFS to the left and right children
29            dfs(node.left)
30            dfs(node.right)
31
32        # Initialize an empty list to store lonely node values
33        lonely_nodes = []
34        # Trigger DFS from the root of the tree
35        dfs(root)
36        # Return the list of lonely node values
37        return lonely_nodes
38
39# Note: The 'Optional' type and 'List' need to be imported from 'typing' module.
40# Example:
41# from typing import List, Optional
42

1// Class to define a binary tree node
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6
7    TreeNode() {}
8
9    TreeNode(int val) {
10        this.val = val;
11    }
12
13    TreeNode(int val, TreeNode left, TreeNode right) {
14        this.val = val;
15        this.left = left;
16        this.right = right;
17    }
18}
19
20class Solution {
21    // List to store the values of lonely nodes
22    private List<Integer> lonelyNodes = new ArrayList<>();
23
24    // Public method to find all lonely nodes
25    public List<Integer> getLonelyNodes(TreeNode root) {
26        // Start depth-first search traversal from root to find lonely nodes
27        dfs(root);
28        return lonelyNodes;
29    }
30
31    // Private helper method to perform depth-first search
32    private void dfs(TreeNode node) {
33        // Base case: if the node is null or it's a leaf (no children)
34        if (node == null || (node.left == null && node.right == null)) {
35            return;
36        }
37        // If the node has no left child, the right child is a lonely node
38        if (node.left == null) {
39            lonelyNodes.add(node.right.val);
40        }
41        // If the node has no right child, the left child is a lonely node
42        if (node.right == null) {
43            lonelyNodes.add(node.left.val);
44        }
45        // Recursively apply DFS to the left subtree
46        dfs(node.left);
47        // Recursively apply DFS to the right subtree
48        dfs(node.right);
49    }
50}
51

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    // Function to collect all lonely nodes in a binary tree
15    vector<int> getLonelyNodes(TreeNode* root) {
16        vector<int> lonelyNodes; // This will hold the lonely nodes, which are nodes that have only one child
17
18        // Define the DFS function to traverse the tree
19        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
20            // Base case: If the node is null or it is a leaf node (no children), return
21            if (!node || (!node->left && !node->right)) return;
22          
23            // If the node only has a right child
24            if (!node->left) {
25                lonelyNodes.push_back(node->right->val); // Add the value of the right child to our answer
26            }
27          
28            // If the node only has a left child
29            if (!node->right) {
30                lonelyNodes.push_back(node->left->val); // Add the value of the left child to our answer
31            }
32          
33            // Recursively call the DFS on the left and right children
34            dfs(node->left);
35            dfs(node->right);
36        };
37
38        // Start DFS traversal from the root
39        dfs(root);
40        // Return the list of lonely nodes found
41        return lonelyNodes;
42    }
43};
44

1// Definition for a binary tree node
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14// This array will hold the lonely nodes, which are nodes that have only one child
15const lonelyNodes: number[] = [];
16
17// The DFS function to traverse the tree
18const dfs = (node: TreeNode | null): void => {
19    // Base case: If the node is null or it is a leaf node (no children), return
20    if (!node || (!node.left && !node.right)) return;
21
22    // If the node only has a right child
23    if (!node.left) {
24        // Add the value of the right child to our answer
25        lonelyNodes.push(node.right.val);
26    }
27
28    // If the node only has a left child
29    if (!node.right) {
30        // Add the value of the left child to our answer
31        lonelyNodes.push(node.left.val);
32    }
33
34    // Recursively call the DFS on the left and right children
35    dfs(node.left);
36    dfs(node.right);
37};
38
39// Function to collect all lonely nodes in a binary tree
40const getLonelyNodes = (root: TreeNode): number[] => {
41    // Start DFS traversal from the root
42    dfs(root);
43    // Return the list of lonely nodes found
44    return lonelyNodes;
45};
46

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the number of nodes in the given binary tree. This complexity arises because the algorithm needs to visit each node exactly once to determine if it has a lonely node (a node with only one child).

Space Complexity

The space complexity of the code is O(h), where h is the height of the binary tree. This is because the depth of the recursive call stack will go as deep as the height of the tree in the worst case. Note that this doesn't include the space taken by the output list ans which, in the worst case, can have up to n - 1 elements if all nodes have only one child. If including the output, the space complexity would be O(n).

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

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

I don't know