DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary

  • Time:2020-09-09 13:08:38
  • Class:Weblog
  • Read:135

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.
binary-tree-lonely-nodes-1 DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary Tree algorithms BFS c / c++ DFS recursive

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.
binary-tree-lonely-nodes-2 DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary Tree algorithms BFS c / c++ DFS recursive

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.
binary-tree-lonely-nodes-3 DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary Tree algorithms BFS c / c++ DFS recursive

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) —

Recommend:
Blogging for Dummies in 2019: The Only Cheat Sheet You Need
Are Readers Reaching Your Call To Action?
How to Manage a Content Marketing Plan for Your Blog
4 Simple Techniques To Bring Your Dead Blog Back To Life
How to Earn Bitcoin Through Blogging
5 PayPal Alternatives for Bloggers and Solopreneurs
Can WordPress Make Other E-commerce Platforms Obsolete?
How to Start a Food Blog (A Step-By-Step 2019 Guide)
3 Possible Solutions to the Most Common Corporate Blogging Probl
Why Social Media is Crucial to Your Marketing Efforts
Share:Facebook Twitter
Comment list
Comment add