SCE questions

mail@pastecode.io avatar
unknown
c_cpp
a year ago
4.1 kB
7
Indexable
Never
//----https://practice.geeksforgeeks.org/problems/height-of-binary-tree/0
class Solution{
    public:
    //Function to find the height of a binary tree.
    int height(struct Node* node){
        // code here 
        if(node == NULL) return 0;
        int lh = height(node->left);
        int rh = height(node->right);
        return 1+max(lh,rh);
    }
};
//---- https://practice.geeksforgeeks.org/problems/maximum-depth-of-binary-tree/0

class Solution{
  public:
    /*You are required to complete this method*/
    int maxDepth(Node *root) {
        // Your code here
        if(root == NULL) return 0;
        int lh = maxDepth(root->left);
        int rh = maxDepth(root->right);
        return 1+max(lh,rh);
    }
};

// ----https://practice.geeksforgeeks.org/problems/level-order-traversal/0

class Solution
{
    public:
    //Function to return the level order traversal of a tree.
    vector<int> levelOrder(Node* node)
    {
      //Your code here
      vector<int> v;
      queue<Node* > q;
      q.push(node);
      while(!q.empty()){
          Node* temp = q.front();
          q.pop();
          v.push_back(temp->data);
        if(temp -> left){
            q.push(temp->left);
        }
        if(temp -> right){
            q.push(temp->right);
        }
      }
      return v;
    }
};
//---- https://practice.geeksforgeeks.org/problems/postorder-traversal/0

void postorder(Node* root, vector<int> &ans){
    if(root==NULL) return;
    postorder(root->left,ans);
    postorder(root->right,ans);
    ans.push_back(root->data);
    
}
//Function to return a list containing the postorder traversal of the tree.
vector <int> postOrder(Node* root)
{
  // Your code here
  vector<int>ans;
  postorder(root,ans);
 return ans;
}

// ---https://practice.geeksforgeeks.org/problems/inorder-traversal/0
}; */

class Solution {
  public:
    // Function to return a list containing the inorder traversal of the tree.
    void inorder(Node* root, vector<int> &ans){
    if(root==NULL) return;
    inorder(root->left,ans);
    ans.push_back(root->data);
    inorder(root->right,ans);
    
}
    vector<int> inOrder(Node* root) {
        // Your code here
        vector<int>ans;
        inorder(root,ans);
        return ans;
    }
};

// ----https://practice.geeksforgeeks.org/problems/bfs-traversal-of-graph/0

class Solution {
  public:
    // Function to return Breadth First Traversal of given graph.
    vector<int> bfsOfGraph(int V, vector<int> adj[]) {
        // creating a visited array of V size
        int visited[V]={0};
        // initially first node is visited
        visited[0]=1;
        // create a queue, push into queue if not completely visited, pop from queue once it is completely visited
        queue<int> q;
        // push into queue once it is visited
        q.push(0);
        // create a vector to store traversed node
        vector<int> bsf;
        // continue till the queue become empty
        while(!q.empty()){
            // get front node
            int node = q.front();
            // remove first element of queue
            q.pop();
            // push into bsf, means it is traversed
            bsf.push_back(node);
            // traverse all the element in adjancency matrix, if it is not visited make it visited and aslo put 
            // it into queue
            for(auto it:adj[node]){
                // if not already visited
                if(!visited[it]){
                    // make it visite
                    visited[it]=1;
                    // also push it into queue
                    q.push(it);
                }
            }
        }
        // once everything is done 
        return bsf;
    }
};

// ----https://practice.geeksforgeeks.org/problems/preorder-traversal/0


void preorder(Node* root, vector<int> &ans){
    if(root==NULL) return;
    ans.push_back(root->data);
    preorder(root->left,ans);
    preorder(root->right,ans);
    
}
//Function to return a list containing the preorder traversal of the tree.
vector <int> preorder(Node* root)
{
  // Your code here
  vector<int>ans;
  preorder(root,ans);
 return ans;
}