Given A binary Tree. Your task is to remove all the half nodes (which has only one child).
The first line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below:
The values in the string are in the order of level order traversal of the tree where, numbers denotes node values, and a character “N” denotes NULL child.
For example:
For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
Output:
Single line output, print the modified tree in the inorder traversal.
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
Node(int val) {
data = val;
left = right = NULL;
}
};
// Function to Build Tree
Node* buildTree(string str)
{
// Corner Case
if(str.length() == 0 || str[0] == 'N')
return NULL;
// Creating vector of strings from input
// string after spliting by space
vector<string> ip;
istringstream iss(str);
for(string str; iss >> str; )
ip.push_back(str);
// Create the root of the tree
Node* root = new Node(stoi(ip[0]));
// Push the root to the queue
queue<Node*> queue;
queue.push(root);
// Starting from the second element
int i = 1;
while(!queue.empty() && i < ip.size()) {
// Get and remove the front of the queue
Node* currNode = queue.front();
queue.pop();
// Get the current node's value from the string
string currVal = ip[i];
// If the left child is not null
if(currVal != "N") {
// Create the left child for the current node
currNode->left = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->left);
}
// For the right child
i++;
if(i >= ip.size())
break;
currVal = ip[i];
// If the right child is not null
if(currVal != "N") {
// Create the right child for the current node
currNode->right = new Node(stoi(currVal));
// Push it to the queue
queue.push(currNode->right);
}
i++;
}
return root;
}
void inorder(Node * node)
{
if(node==NULL)
return;
inorder(node->left);
cout<<node->data<<" ";
inorder(node->right);
}
Node* RemoveHalfNodes(Node* root) ;
int main()
{
int t;
scanf("%d ",&t);
while(t--)
{
string s;
getline(cin,s);
Node* root = buildTree(s);
Node * fresh = RemoveHalfNodes(root);
inorder(fresh);
cout<<endl;
}
return 1;
}// } Driver Code Ends
/*Complete the function below
Node is as follows:
struct Node {
int data;
Node *left;
Node *right;
Node(int val) {
data = val;
left = right = NULL;
}
};
*/
// Return the root of the modified tree after removing all the half nodes.
Node *removeNodes(Node *root)
{
// if root is null then return null
if(root==NULL)
return NULL;
// if both left and right are null return root this is leave node
if(root->left==NULL&&root->right==NULL)
return root;
// recurcive call left subtree
root->left=removeNodes(root->left);
// recurcive call right subtree
root->right=removeNodes(root->right);
// if root has only left child then root is replace by its left child
if(root->left!=NULL&&root->right==NULL)
{
return (root->left);
}
// if root has only
if(root->left==NULL&&root->right!=NULL)
{
return (root->right);
}
return root;
}
Node *RemoveHalfNodes(Node *root)
{
//add code here.
return removeNodes(root);
}
