Normal BST to Balanced BST | Practice | GeeksforGeeks

class Solution{
    
    public:
    // Your are required to complete this function
    // function should return root of the modified BST
    void inorder(Node* root, vector<int>& bst){
        if(!root)
            return;
        inorder(root->left, bst);
        bst.push_back(root->data);
        inorder(root->right, bst);
    }
    
    Node* build(int l , int r, vector<int>& bst){
        if(l > r)
            return nullptr;
        if(l == r)
            return new Node(bst[l]);
        int m = (l + r)/2;
        Node* root = new Node(bst[m]);
        root->left = build(l, m-1,bst);
        root->right = build(m+1,r,bst);
        return root;
    }
    Node* buildBalancedTree(Node* root)
    {
    	// Code here
    	vector<int> bst;
    	inorder(root, bst);
    	return build(0, bst.size() - 1, bst);
    }
};

class Solution {
public:
    int numOfWays(vector<int>& nums) {
        int m = nums.size();
        
        table.resize( m + 1);
        for(int i = 0; i < m + 1; ++i){
            table[i] = vector<long long> (i+1, 1);
            for(int j = 1; j < i ; ++j)
                table[i][j] = (table[i-1][j-1] + table[i-1][j])%mod;
        }
        return (dfs(nums) - 1) % mod;
    }
private:
    vector<vector<long long>> table;
    long long mod = 1e9+7;
    
    long long dfs(vector<int>& nums){
        int m = nums.size();
        if( m  < 3)
            return 1;
        vector<int> leftNodes, rightNodes;
        for(int i = 1; i < m ; i++){
            if( nums[i] < nums[0])
                leftNodes.push_back(nums[i]);
            else
                rightNodes.push_back(nums[i]);
        }
        long long leftWays = dfs(leftNodes) % mod;
        long long rightWays = dfs(rightNodes) % mod;
        return (((leftWays * rightWays) % mod) * table[m-1][leftNodes.size()])%mod;
    }
};

class Solution{

public:
    int searchBST(Node* root, int target, int ans = -1){
        if(!root){
            return ans;
        }
        if(root->data <= target){
            ans = root->data;
            return searchBST(root->right,target, ans);
        }
        return searchBST(root->left, target, ans);
        
    }
    int floor(Node* root, int x) {
        // Code here
        if(!root )  return -1;
        return searchBST(root, x);
    }
};

class Solution {
public:
	//assume you are standing at the ith index and you ask should I choose (i-1)th or (i-2)th to reach the ith position then choose whichever is lesser in cost.
	// ex - > [2,3,1,1,1,4,2,1,3]
	// we insert 0 at beginning and end
	// [0,2,3,1,1,1,4,2,1,3,0], n = 11
	//we start the iteration from 2nd index 
	// [0,2,_,_,_,_,_,_,_,_,_]
	// [0,2,3,_,_,_,_,_,_,_,_]
	// [0,2,3,3,_,_,_,_,_,_,_]
	// [0,2,3,3,4,_,_,_,_,_,_]
	// [0,2,3,3,4,4,_,_,_,_,_]
	// [0,2,3,3,4,4,8,_,_,_,_]
	// [0,2,3,3,4,4,8,6,_,_,_]
	// [0,2,3,3,4,4,8,6,7,_,_]
	// [0,2,3,3,4,4,8,6,7,9,_]
	// [0,2,3,3,4,4,8,6,7,9,7]
	// our answer is 7;

    int minCostClimbingStairs(vector<int>& cost) {
        cost.insert(cost.begin() + 0, 0);
        cost.push_back(0);
        vector<int> dp(cost);
        for(int i = 2; i < dp.size() ; i++)
            dp[i] = dp[i] + min(dp[i-1],dp[i-2]);
        return dp.back();
    }
};

class Solution
{
	public:
	//Function to find the level of node X.
	using pi = pair<int,int>;
	int nodeLevel(int V, vector<int> adj[], int X) 
	{
	    // code here
	    vector<bool> vis(V, false);
	    queue<pi> q;
	    q.push({0, 0});
	    vis[0] = true;
	    while(!q.empty()){
	        auto curr = q.front();q.pop();
	        if(curr.first == X)
	            return curr.second;
	       for(auto adjV : adj[curr.first]){
	           if(!vis[adjV]){
	               vis[adjV] = true;
	               q.push({adjV , curr.second + 1});
	           }
	       }
	    }
	    return -1;
	}
};