In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node. Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.

Example 1:
Input: root = [1,2,3,null,4]
Output: [4]
Explanation: Light blue node is the only lonely node.
Node 1 is the root and is not lonely.
Nodes 2 and 3 have the same parent and are not lonely.

Example 2:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn’t matter, [2,6] is also an acceptable answer.

Example 3:
Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22]
Output: [77,55,33,66,44,22]
Explanation: Nodes 99 and 88 share the same parent. Node 11 is the root.
All other nodes are lonely.

Example 4:
Input: root = [197]
Output: []

Example 5:
Input: root = [31,null,78,null,28]
Output: [78,28]

Constraints:

The number of nodes in the tree is in the range [1, 1000].
Each node’s value is between [1, 10^6].

Hints:
Do a simple tree traversal, try to check if the current node is lonely or not.
Node is lonely if at least one of the left/right pointers is null.

Depth First Search Algorithm Finding Lonely Nodes of Binary Tree

We can recursively traverse the binary tree from the root to the leaves. As we are at parent nodes first, we know exactly the number of children for the current parent. We push the lonely nodes as we go down to the leaves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }
    
private:
    void dfs(TreeNode* root, vector<int> &res) {
        if (!root) return;
        if ((root->left) && (root->right)) {
            dfs(root->left, res);
            dfs(root->right, res);
            return;
        }
        if (root->left) {
            res.push_back(root->left->val);        
            dfs(root->left, res);
        }
        if (root->right) {
            res.push_back(root->right->val);        
            dfs(root->right, res);            
        }                
    }
};

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> res;
        dfs(root, res);
        return res;
    }
    
private:
    void dfs(TreeNode* root, vector<int> &res) {
        if (!root) return;
        if ((root->left) && (root->right)) {
            dfs(root->left, res);
            dfs(root->right, res);
            return;
        }
        if (root->left) {
            res.push_back(root->left->val);        
            dfs(root->left, res);
        }
        if (root->right) {
            res.push_back(root->right->val);        
            dfs(root->right, res);            
        }                
    }
};

The DFS algorithm can also be implemented based on the stack – without Recursion. This is actually quite similar to the BFS approach where you would use a stack instead of a queue.

How to Find Lonely Nodes of a Binary Tree using Breadth First Search Algorithm?

The Breadth First Search (BFS) algorithm traverses the tree level by level, and as we are expanding the children into the queue, we save the lonely nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if ((p->left) && (p->right)) {
                Q.push(p->left);
                Q.push(p->right);
                continue;
            }
            if (p->left) {
                Q.push(p->left);
                res.push_back(p->left->val);
                continue;
            }
            if (p->right) {
                Q.push(p->right);
                res.push_back(p->right->val);            
            }
        }        
        return res;
    }
};

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> Q;
        Q.push(root);
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            if ((p->left) && (p->right)) {
                Q.push(p->left);
                Q.push(p->right);
                continue;
            }
            if (p->left) {
                Q.push(p->left);
                res.push_back(p->left->val);
                continue;
            }
            if (p->right) {
                Q.push(p->right);
                res.push_back(p->right->val);            
            }
        }        
        return res;
    }
};

Both implementations are O(N) time and O(N) space where N is the number of the nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —