Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def getLonelyNodes(self, root):
        lonely = []
        def dfs(node):
            if not node:
                return
            if node.left and not node.right:
                lonely.append(node.left.val)
            if node.right and not node.left:
                lonely.append(node.right.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return lonely
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> lonely;
        dfs(root, lonely);
        return lonely;
    }
    void dfs(TreeNode* node, vector<int>& lonely) {
        if (!node) return;
        if (node->left && !node->right)
            lonely.push_back(node->left->val);
        if (node->right && !node->left)
            lonely.push_back(node->right->val);
        dfs(node->left, lonely);
        dfs(node->right, lonely);
    }
};
      

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> lonely = new ArrayList<>();
        dfs(root, lonely);
        return lonely;
    }
    private void dfs(TreeNode node, List<Integer> lonely) {
        if (node == null) return;
        if (node.left != null && node.right == null)
            lonely.add(node.left.val);
        if (node.right != null && node.left == null)
            lonely.add(node.right.val);
        dfs(node.left, lonely);
        dfs(node.right, lonely);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
var getLonelyNodes = function(root) {
    let lonely = [];
    function dfs(node) {
        if (!node) return;
        if (node.left && !node.right)
            lonely.push(node.left.val);
        if (node.right && !node.left)
            lonely.push(node.right.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return lonely;
};
      

Problem Description

Given the root of a binary tree, your task is to find all lonely nodes in the tree. A lonely node is a node that is the only child of its parent, meaning its parent has exactly one child. The root node is never lonely because it has no parent.

Return a list of the values of all lonely nodes in any order.

• Each node in the tree has a unique integer value.
• The input is the root node of the binary tree.
• The output is a list (or array) of integers representing the values of all lonely nodes.
• There may be zero, one, or multiple lonely nodes in the tree.

Thought Process

To solve this problem, we need to traverse the tree and identify nodes that are the only child of their parent. In other words, for every parent node, if it has exactly one child (either left or right, but not both), then that child is considered lonely.

A brute-force approach would be to check every node and see if its parent has only one child, but since we typically traverse from the root down, it's more convenient to check each parent node and append its only child (if any) to our answer list.

This leads us to a recursive traversal (like depth-first search) where, at each node, we check if it has exactly one child, and if so, record that child. We continue recursively for both left and right children.

This method is both simple and efficient, as we only need to visit each node once.

Solution Approach

• Step 1: Traverse the Tree
  • We use depth-first search (DFS) starting from the root node.
  • At each node, we check if it has only one child.
• Step 2: Identify Lonely Nodes
  • If the current node has a left child but no right child, the left child is lonely.
  • If the current node has a right child but no left child, the right child is lonely.
• Step 3: Collect Results
  • Each time we find a lonely node, we add its value to our result list.
• Step 4: Return the Result
  • After the traversal is complete, return the list of lonely node values.

This approach ensures that every node is visited only once, resulting in an efficient solution.

Example Walkthrough

Let's consider the following binary tree:

        1
       / \
      2   3
       \
        4
         \
          5
  

• Start at node 1 (root):
  • Has both left and right children, so no lonely node here.
• Move to node 2 (left child of 1):
  • Has no left child, but has right child 4 — so 4 is lonely.
• Move to node 3 (right child of 1):
  • Has no children, so nothing to check.
• Move to node 4 (right child of 2):
  • Has no left child, but has right child 5 — so 5 is lonely.
• Node 5 (right child of 4) has no children.

Result: The lonely nodes are 4 and 5.

Time and Space Complexity

• Brute-force approach:
  • If you tried to keep parent pointers or traverse the tree multiple times, you might end up with O(N^2) time in the worst case, where N is the number of nodes.
• Optimized approach (DFS):
  • Each node is visited exactly once, so the time complexity is O(N).
  • The space complexity is also O(N) in the worst case due to the recursion stack (for a skewed tree) and the result list.

This makes the DFS approach both time and space efficient for this problem.

Summary

We solved the "Tree Node" problem by performing a depth-first traversal of the binary tree, checking at each step if a node is the only child of its parent. By collecting all such "lonely" nodes, we efficiently build the answer in a single pass through the tree. The approach is elegant because it leverages the natural recursive structure of trees and avoids unnecessary work, ensuring optimal time and space complexity.