Given the root of a binary tree, a lonely node is a node that has no siblings (i.e., it’s the only child of its parent). Return an array containing the values of all lonely nodes in the tree, sorted in ascending order.
Table of Contents
Sample Input:
Tree:
1
/ \
2 3
/ / \
4 5 6
\
7
Expected Output:
[4, 6]
In this example, the lonely nodes are nodes with values 4 and 6, as they have no siblings.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to identify the lonely nodes. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
#include <vector>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void findLonelyNodes(TreeNode* root, std::vector<int>& lonelyNodes) {
// Base case: if the root is null, return
if (root == nullptr) {
return;
}
// Check if the current node is lonely (has no siblings)
if ((root->left && !root->right) || (!root->left && root->right)) {
// If the current node is lonely, add its value to the lonelyNodes vector
lonelyNodes.push_back(root->val);
}
// Recursively search for lonely nodes in the left and right subtrees
findLonelyNodes(root->left, lonelyNodes);
findLonelyNodes(root->right, lonelyNodes);
}
std::vector<int> getLonelyNodes(TreeNode* root) {
std::vector<int> lonelyNodes;
findLonelyNodes(root, lonelyNodes);
return lonelyNodes;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);
root->right->left->right = new TreeNode(7);
// Find the lonely nodes in the binary tree
std::vector<int> lonelyNodes = getLonelyNodes(root);
// Print the result
std::cout << "Lonely Nodes: [";
for (int i = 0; i < lonelyNodes.size(); ++i) {
std::cout << lonelyNodes[i];
if (i < lonelyNodes.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The findLonelyNodes function recursively searches for lonely nodes in the binary tree. It checks if the current node has no siblings (only one child) and adds its value to the lonelyNodes vector if it is lonely. The getLonelyNodes function is a wrapper function that calls the recursive findLonelyNodes function and returns the result.
In the given example, the function will correctly find the lonely nodes with values [4, 6], and the output will be [4, 6].
The time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.