1469. Find All The Lonely Nodes
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.
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. Theroot
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
isNone
, 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.
- If the
-
For each non-null node visited by
dfs
, the function checks if the node has a single child. This is verified by checking ifroot.left
isNone
when a right child exists, orroot.right
isNone
when a left child exists. -
If the node has only one child, the value of that lonely child node (
root.right.val
orroot.left.val
) is added to theans
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 namedans
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 theroot
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
isNone
. Since 1 has children, it's notNone
, 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)
anddfs(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) toans
. - 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.
How does quick sort divide the problem into subproblems?
Recommended Readings
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
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
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
Want a Structured Path to Master System Design Too? Don’t Miss This!