```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 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:
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;
}
};```
star

Sun Oct 15 2023 11:44:12 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/normal-bst-to-balanced-bst/1

#bst #balancebst #easy
star

Fri Oct 13 2023 03:51:39 GMT+0000 (Coordinated Universal Time) https://practice.geeksforgeeks.org/problems/floor-in-bst/1

#bst #binarysearchtree #floor
star

Fri Jun 16 2023 07:57:40 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

#c++ #dfs #bst #dynamic_programming #combinatorics