bkb181

gf

bkb181

   fd

bkb181

|     Approaches           | Time Complexity  | Space Complexity |
+==================+=================+===========================+
| Recursive Approach       |O(n^n)            | O(n)             |
+------------------+--------------------+------------------------+
| Dynamic Programming      | O(n^2)           | O(n)             |
+------------------+--------------------+------------------------+

bkb181

|     Approaches           | Time Complexity  | Space Complexity |
+==================+=================+===========================+
| Recursive Approach       |O(n^n)            | O(n)             |
+------------------+--------------------+------------------------+
| Dynamic Programming      | O(n^2)           | O(n)             |
+------------------+--------------------+------------------------+

bkb181

int rod_cut(int price[], int n)
{
  if(n== 0)
  return 0;
  int profit = INT_MIN;
  for(int i = 1; i <= n; i++)
  {
    int cost= price[i-1] + rod_cut(price, n-i);
    profit=max(cost, profit);
  }

bkb181

int rod_cut(int price[], int n)
{
  int T[n+1], i, j;
  for (int i = 0; i <= n; i++)
  T[i] = 0;
  for(i= 1; i<= n; i++)
  {
    for(j= 1; j<= i; j++)
    T[i]= max(T[i], price[j-1] + T[i - j]);
  }

bkb181

|     Approaches           | Time Complexity  | Space Complexity |
+==================+=================+===========================+
| Inorder Approach         |O(n+m)              | O(n+m)           |
+------------------+--------------------+------------------------+
| Stack Based Approach     | O(n+m)             | O(max(m,n))    |
+------------------+--------------------+------------------------+

bkb181

void merge_bst(node* root1, node* root2)
  {
  stack<node * > s1;
  stack<node * > s2;
  vector<int> res;
  node * temp1= root1;
  node * temp2= root2;
  while(temp1!=NULL){
  s1.push(temp1);
  temp1= temp1->left;

bkb181

void inorder(node* root,vector<int>& res)
{
if(A==NULL)
return;
inorder(A->left, res);
res.push_back(root->data);
inorder(A->right, res);
}
void merge_bst(node* root1, node* root2)
{

bkb181

|     Approaches           | Time Complexity  | Space Complexity |
+==================+=================+===========================+
| Preorder Approach        |O(n)              | O(n)             |
+------------------+--------------------+------------------------+
| Level Order Approach     | O(n)             | O(n)             |
+------------------+--------------------+------------------------+