Tree goodbye

 #include<iostream>

#include<vector>

#include<queue>

using namespace std;

template <typename T>



class TreeNode {

    public:

    T data;

    vector<TreeNode<T>*>children;

    

    TreeNode(T data){

        this->data=data;

    }

};


void printTree(TreeNode<int>* root){

    cout<<root->data<<":";

    for (int i=0;i<root->children.size();i++){

        cout<<root->children[i]->data<<",";

    }

    cout<<endl;

    for (int i=0;i<root->children.size();i++){

        printTree(root->children[i]);

    }

}


TreeNode<int>* takeInput(){

    int rootData;

    cout<<"Enter Data: ";

    cin>>rootData;

     TreeNode <int>* root = new TreeNode<int>(rootData);

    cout<<"Enter number of children of "<<rootData<<": ";

    int n;

    cin>>n;

    for(int i=0;i<n;i++){

        TreeNode<int>*child=takeInput();

        root->children.push_back(child);

    }

    return root;

    

    

    

}


TreeNode<int>* takeInputLevel(){

    int rootData;

    cout<<"Enter Data: "<<endl;

    cin>>rootData;

    TreeNode <int>* root = new TreeNode<int>(rootData);

    queue<TreeNode<int>*> pendingNode;//queue

    pendingNode.push(root);

    while(pendingNode.size()!=0){

        TreeNode<int>*front = pendingNode.front();

        pendingNode.pop();

        cout<<"Enter the number of children of "<<front->data<<endl;

        int childnum;

        cin>>childnum;

        for (int i=0;i<childnum;i++){

            cout<<"Enter the "<<i<<"th data of root"<<front->data<<endl;

            int childata;

            cin>>childata;

            TreeNode <int>* child = new TreeNode<int>(childata);

            pendingNode.push(child);

            front->children.push_back(child);

        }

    }

    return root;

}


void printLevelWise(TreeNode<int>* root) {

    // Write your code here

    

    queue<TreeNode<int>*> pendingNode;//queue

    pendingNode.push(root);

    

    while(pendingNode.size()!=0){

        TreeNode<int>* front=pendingNode.front();//front -> current root/ first ele of q

    pendingNode.pop();

        cout<<front->data<<":";

        

        //int n;

       // cin>>n;

        for(int i=0;i<front->children.size();i++){

            if (i==front->children.size()-1){

                cout<<front->children[i]->data;

            }

            else{

            

            cout<<front->children[i]->data<<",";

            }

            pendingNode.push(front->children[i]);

            

        }

        

        cout<<endl;

        

        

    }

    

    

       

        

}


int numNodes(TreeNode<int>* root){

    int ans=1;

    for(int i=0;i<root->children.size();i++){

        ans+=numNodes(root->children[i]);

    }

    return ans;

}


void printAtLevel(TreeNode<int>* root, int k){

    if (root==NULL){

        return;

    }

    if (k==0){

        cout<<root->data<<" ";

        return;

    }

    for (int i=0;i<root->children.size();i++){

        printAtLevel(root->children[i],k-1);

    }

}


void preorder(TreeNode<int>* root){

    if(root==NULL){

        return;

    }

    

    for(int i=0;i<root->children.size();i++){

        preorder(root->children[i]);

    }

    cout<<root->data<<" ";

}

int main(){

    // TreeNode<int>* root=new TreeNode<int>(1);

    // TreeNode<int>* node1=new TreeNode<int>(2);

    // TreeNode<int>* node2=new TreeNode<int>(3);

    

    // root->children.push_back(node1);

    // root->children.push_back(node2);

    TreeNode<int>*root=takeInputLevel();

    preorder(root);

    cout<<endl;

    printLevelWise(root);

    cout<<endl;

    cout<<"At level 2 ";

    printAtLevel(root,2);

    cout<<endl;

    cout<<numNodes(root);

}

Comments

Post a Comment

Popular posts from this blog

Sum of Even Numbers till N

Given a number N, print sum of all even numbers from 1 to N. #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){         if (i%2==0){             sum=sum+i;         }     }     cout<<sum;    } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<iostream> using namespace std; int main(){        /*  Read input as specified in the question. * Print output as specified in the question. */     int sum,n;     cin>>n;     sum=0;     for (int i=1;i<=n;i++){     ...
Read more

Find the Runner-Up Score!

  Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given     scores. Store them in a list and find the score of the runner-up. Input Format The first line contains  . The second line contains an array     of   integers each separated by a space. Constraints Output Format Print the runner-up score. Sample Input 0 5 2 3 6 6 5 Sample Output 0 5 Explanation 0 Given list is  . The maximum score is  , second maximum is  . Hence, we print   as the runner-up score. ### OPTIMIZED ### from   collections   import   Counter if  __ name__  ==  '__main__' :      n  =  int ( input ())      arr  =  map ( int ,   input () . split ())           lis = list ( Counter ( arr ) . keys ())      lis . sort ()  ...
Read more

Print All Substrings

  For a given input string(str), write a function to print all the possible substrings. Substring A substring is a contiguous sequence of characters within a string. Example: "cod" is a substring of "coding". Whereas, "cdng" is not as the characters taken are not contiguous Input Format: The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case. Output Format: Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings. Note: The order in which the substrings are printed, does not matter. Constraints: 0 <= N <= 10^6 Where N is the length of the input string. Time Limit: 1 second Sample Input 1: abc Sample Output 1: a ab abc b bc c  Sample Input 2: co Sample Output 2: c co o #include <iostream> #include <cstring> us...
Read more