Author: thecodepathshala

void pre(Node *root, vector<int> &ans) {
        if(!root) {
            ans.push_back(-1);
            return;
        }
        ans.push_back(root->data);
        pre(root->left, ans);
        pre(root->right, ans);
    }
    // Function to serialize a tree and return a list containing nodes of tree.
    vector<int> serialize(Node *root) {
        // Your code here
        vector<int> ans;
        pre(root, ans);
        return ans;
    }

    int i = 0;
    // Function to deserialize a list and construct the tree.
    Node *deSerialize(vector<int> &arr) {
        // Your code here
        int val = arr[i];
        i++;
        if(val == -1) return NULL;
        Node *tmp = new Node(val);
        tmp->left = deSerialize(arr);
        tmp->right = deSerialize(arr);
        return tmp;
    }

bool isLeaf(Node *root) {
        if(root->left == NULL && root->right == NULL)
            return true;
        return false;
    }
    void leftBoundry(Node *root, vector<int> &res) {
        if(root == NULL || isLeaf(root)) return;
        res.push_back(root->data);
        if(root->left) leftBoundry(root->left, res);
        else if(root->right) leftBoundry(root->right, res);
    }
    void leafBoundry(Node *root, vector<int> &res) {
        if(root == NULL) return;
        if(isLeaf(root)) {
            res.push_back(root->data);
            return;
        }
        leafBoundry(root->left, res);
        leafBoundry(root->right, res);
    }
    void rightBoundry(Node *root, vector<int> &res) {
        if(root == NULL || isLeaf(root)) return;
        if(root->right) rightBoundry(root->right, res); 
        else if(root->left) rightBoundry(root->left, res);
        res.push_back(root->data);
    }
    vector<int> boundaryTraversal(Node *root) {
        // code here
        vector<int> res;
        if(!root) return res;
        if(!isLeaf(root)) res.push_back(root->data);
        leftBoundry(root->left, res);
        leafBoundry(root, res);
        rightBoundry(root->right, res);
        
        return res;
    }

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

int height(Node* node, int &dia) {
        // code here
        if(node == NULL) return 0;
        int lh = height(node->left,dia);
        int rh = height(node->right,dia);
        dia = max(dia, lh+rh);
        return max(lh, rh) +1;
    }
    int diameter(Node* root) {
        // Your code here
        int diameter = 0;
        height(root, diameter);
        return diameter;
    }

vector<vector<int>> levelOrder(Node *root) {
        // Your code here
        vector<vector<int>> ans;
        if(root == NULL) return ans;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            vector<int> res;
            int len = q.size();
            for(int i=0; i<len; i++) {
                Node *cur = q.front();
                q.pop();
                res.push_back(cur->data);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            ans.push_back(res);
        }
        return ans;
    }

bool solve(vector<vector<char>>& mat, string& word, int i, int j, int widx) {
        int wlen = word.length();
        int n = mat.size();
        int m = mat[0].size();
        //base case
        if(widx == wlen) return true;
        if(i<0 || j<0 || i>=n || j>=m) return false;
        //recursive case
        if(mat[i][j] == word[widx]) {
            bool res = false;
            char tmp = mat[i][j];
            mat[i][j] = '_';
            if(solve(mat, word, i-1, j, widx+1) || solve(mat, word, i+1, j, widx+1) ||
                solve(mat, word, i, j+1, widx+1) || solve(mat, word, i, j-1, widx+1)) 
                    res = true;
            mat[i][j] = tmp;
            return res;
        }
        return false;
    }
    bool isWordExist(vector<vector<char>>& mat, string& word) {
        // Code here
        int n = mat.size();
        int m = mat[0].size();
        int wlen = word.length();
        for(int i=0;i<n; i++) {
            for(int j=0; j<m; j++) {
                if(solve(mat, word, i, j, 0)) return true;
            }
        }
        return false;
    }

bool setisfy(vector<vector<int>> &mat, int i, int j, int num) {
        for(int x= 0; x<9; x++) {
            if(mat[i][x] == num || mat[x][j] == num) 
                return false;
        }
        int str = i-i%3, stc = j-j%3;
        for(int a=0; a<3; a++){
            for(int b=0;b<3; b++) {
                if(mat[str+a][stc+b] == num)
                    return false;
            }
        }
        return true;
    }
    
    bool solve(vector<vector<int>> &mat)  {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if(mat[i][j] == 0) {
                    for(int num = 1; num<=9; num++) {
                        if(setisfy(mat, i, j, num)) {
                            mat[i][j] = num;
                            if(solve(mat)) return true;
                            mat[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    // Function to find a solved Sudoku.
    void solveSudoku(vector<vector<int>> &mat) {
        // code here
        solve(mat);
    }

void solve(int colm, int n, vector<bool> &col, vector<bool> &ldiag, vector<bool> &rdiag, vector<vector<int>> &ans, vector<int> &res) {
        for(int i=0; i<n; i++) {
            if(colm == n) {
                ans.push_back(res);
                return;
            }
            if(!col[i] && !ldiag[colm-i + n-1] && !rdiag[i+colm]) {
                res.push_back(i+1);
                col[i] = true;
                ldiag[colm-i+n-1] = true;
                rdiag[i+colm] = true;
                solve(colm+1, n, col, ldiag, rdiag, ans, res);
                
                res.pop_back();
                col[i] = false;
                ldiag[colm-i+n-1] = false;
                rdiag[i+colm] = false;
                
            }
        }
        
    }
    vector<vector<int>> nQueen(int n) {
        // code here
        vector<bool>col(n, false);
        vector<bool>ldiag(2*n-1, false);
        vector<bool>rdiag(2*n-1, false);
        vector<vector<int>> ans;
        vector<int> res;
        solve(0, n, col, ldiag, rdiag, ans, res);
        return ans;
    }