1469. Find All The Lonely Nodes

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. The dfs function is called with the root of the binary tree as its argument, starting the traversal.

  8. 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.

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

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

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

1    1
2   / \
3  2   3
4 /   / \
54   5   null
6   /
7  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:

  1. We define dfs(root), which we'll call on the root node (1 in our example).
  2. 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.
  3. We check if node 1 has a single child. It has two, so no nodes are added to the ans list.
  4. 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.
  1. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a min heap?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ