{x}
blog image

Find All The Lonely Nodes

1469. Find All The Lonely Nodes

Problem Description

Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. A lonely node is a node that is the only child of its parent node. The root of the tree is not considered a lonely node.

Solution: Depth-First Search (DFS)

This problem can be efficiently solved using Depth-First Search (DFS). The algorithm traverses the tree recursively, checking each node to see if it's a lonely node.

Algorithm:

  1. Base Case: If the current node is null or a leaf node (both left and right children are null), return.
  2. Lonely Node Check:
    • If the current node has only a left child (right is null), add the left child's value to the result list.
    • If the current node has only a right child (left is null), add the right child's value to the result list.
  3. Recursive Calls: Recursively call the DFS function for the left and right subtrees.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂(N).

Code Implementation

Here are implementations in several programming languages:

Python:

# 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
 
class Solution:
    def getLonelyNodes(self, root: TreeNode) -> List[int]:
        result = []
 
        def dfs(node):
            if not node:
                return
            if node.left and not node.right:
                result.append(node.left.val)
            if node.right and not node.left:
                result.append(node.right.val)
            dfs(node.left)
            dfs(node.right)
 
        dfs(root)
        return result

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
 
class Solution {
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
 
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        if (node.left != null && node.right == null) {
            result.add(node.left.val);
        }
        if (node.right != null && node.left == null) {
            result.add(node.right.val);
        }
        dfs(node.left, result);
        dfs(node.right, result);
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
 
class Solution {
public:
    std::vector<int> getLonelyNodes(TreeNode* root) {
        std::vector<int> result;
        dfs(root, result);
        return result;
    }
 
private:
    void dfs(TreeNode* node, std::vector<int>& result) {
        if (!node) {
            return;
        }
        if (node->left && !node->right) {
            result.push_back(node->left->val);
        }
        if (node->right && !node->left) {
            result.push_back(node->right->val);
        }
        dfs(node->left, result);
        dfs(node->right, result);
    }
};

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var getLonelyNodes = function(root) {
    let result = [];
    function dfs(node) {
        if (!node) return;
        if (node.left && !node.right) result.push(node.left.val);
        if (node.right && !node.left) result.push(node.right.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return result;
};

These codes all follow the same algorithm and achieve the same result with the specified time and space complexities. Choose the implementation that best suits your preferred programming language.