Home
DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary Tree
Tags:, , , , ,

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

June 4, 2020 No Comments algorithms, BFS, c / c++, DFS, recursive

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.

Another BFS implementation is slightly different:

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) {
        if (!root) return {};
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        vector<int> ans;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left) q.push({p.first->left, countChildren(p.first)});
            if (p.first->right) q.push({p.first->right, countChildren(p.first)});
            if (p.second == 1) {
                ans.push_back(p.first->val);
            }
        }
        return ans;
    }
private:
    int countChildren(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;
        if (root->left) ans ++;
        if (root->right) ans ++;
        return ans;
    }
};
/**
 * 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) {
        if (!root) return {};
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        vector<int> ans;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left) q.push({p.first->left, countChildren(p.first)});
            if (p.first->right) q.push({p.first->right, countChildren(p.first)});
            if (p.second == 1) {
                ans.push_back(p.first->val);
            }
        }
        return ans;
    }
private:
    int countChildren(TreeNode* root) {
        if (!root) return 0;
        int ans = 0;
        if (root->left) ans ++;
        if (root->right) ans ++;
        return ans;
    }
};

In this BFS, we have also implemented a countChildren function, and then when each node is pop from the queue, we check the children nodes of its parent. In other words, when we push the children to the queue, we also have to record the current children count of the node.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1032 words
Last Post: Three ways of Running a continuous NodeJS Application on Your Server
Next Post: Illustrating the Blockchain via SteemJs - Blocks are Chained

The Permanent URL is: DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary Tree

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  3. The Review of cozmo robot from Anki The ANKI COZMO robot is fun – I got it from Amazon and it is...
  4. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  5. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  6. How to Find the Kth Smallest Element in a BST Tree Using Java/C++? Given a binary search tree, write a function kthSmallest to find the kth smallest element...
  7. Teaching Kids Programming – Recursive Algorithm to Prune a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  8. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...

Leave a Reply