Given a binary tree output should have the node values as sum of all the children data and its node data

Input tree:                  Output tree:

C++ Program:

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
}

void postorder(struct node* root)
{
 if(root)
 {
     postorder(root->left);
     postorder(root->right);
     if(root->left)
     {
         root->data=root->data+root->left->data;
     }
     if(root->right)
     {
         root->data=root->data+root->right->data;
     }
 }
}

int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}

void levelorderprint(struct node* root,int level)
{
 if(root && level==0)
 {
  cout<<root->data<<" ";
 }
 else if(root)
 {
  levelorderprint(root->left,level-1);
  levelorderprint(root->right,level-1);
 }
}

void levelorder(struct node* root)
{
 int h=height(root);
 for(int i=0;i<h;i++)
 {
  levelorderprint(root,i);
  cout<<endl;
 }
}

int main()
{
        struct node* root1=createnode(1);
 root1->left=createnode(2);
 root1->right=createnode(3);
 root1->left->right=createnode(5);
 root1->left->left=createnode(4);
 root1->right->right=createnode(7);
 root1->right->left=createnode(6);
 //root1->right->right->left=createnode(8);
 cout<<"The input tree is:\n";
 levelorder(root1);
 postorder(root1);
 cout<<"The sum tree is\n";
 levelorder(root1);
}
Output:
The input tree is:
1
2 3
4 5 6 7
The sum tree is
28
11 16
4 5 6 7

Process returned 0 (0x0)   execution time : 0.016 s
Press any key to continue.

Right Neighbour of nodes in a Binary Tree

Given a binary tree with nodes that have left, right pointers pointing to the left and right children respoectively. Each node also has a right-neighbor pointer that currently points to null.
Write a function to make it point to its neighbor.

Example:
Input tree
1
2 3
4 5 6 7
Expected configuration of the tree
1 right-neighbour should point to null
2 right-neighbour should point to 3
3 right-neighbour should point to null
4 right-neighbour should point to 5
5 right-neighbour should point to 6
6 right-neighbour should point to 7
7 right-neighbour should point to null

Approach
1. Do a level-order traversal of the binary tree.
2. During this traversal keep track of the current root you visit in a level.
3. The next time you visit a root in the same level, make the right-neighbour pointer of the current root to point to this root.
4. Update the current pointer to this root.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
 struct node* right_neighbour;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 new_node->right_neighbour=NULL;
 return new_node;
}

int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}

void levelorderprint(struct node* root,int level,struct node** current)
{
 if(root && level==0)
 {
  cout<<root->data<<" ";
  if(*current == NULL)
  {
      *current = root;
  }
  else
  {
      (*current)->right_neighbour=root;
      *current=root;
  }
 }
 else if(root)
 {
  levelorderprint(root->left,level-1,current);
  levelorderprint(root->right,level-1,current);
 }
}
void levelorder(struct node* root)
{
 int h=height(root);
 struct node* addr=NULL;
 struct node** current=&addr;
 for(int i=0;i<h;i++)
 {
     addr=NULL;//Very important step because addr gets changed in the function levelorderprint as its address is passed.
     current=&addr;
     levelorderprint(root,i,current);
     cout<<endl;
 }
}

void inorder(struct node* root)
{
        if(root)
 {
  inorder(root->left);
  cout<<root->data;
  if(!root->right_neighbour)
  {
      cout<<endl;
  }
  else
  {
      cout<<"->"<<root->right_neighbour->data<<endl;
  }
  inorder(root->right);
 }
}

int main()
{
    struct node* root1=createnode(1);
    root1->left=createnode(2);
    root1->right=createnode(3);
    root1->left->right=createnode(5);
    root1->left->left=createnode(4);
    root1->right->right=createnode(7);
    root1->right->left=createnode(6);
    root1->right->right->left=createnode(8);
    cout<<"The input tree is\n";
    levelorder(root1);
    cout<<"The right neighbours are:\n";
    inorder(root1);
}
Output:
1
2 3
4 5 6 7
8
The right neighbours are:
4->5
2->3
5->6
1
6->7
3
8
7

Process returned 0 (0x0)   execution time : 0.056 s
Press any key to continue.

Gambling game

In a game, you bet using the following strategy. Whenever you lose a bet, you double the value of the bet for the next round. Whenever you win, the bet for the next round will be one dollar. You start the round by betting one dollar.

For example, if you start with 20 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 20+1-1-2+4 = 22 dollars.

You are expected to complete the function, getFinalAmount, which takes two arguments. The first argument is an integer initialAmount which is the initial money we amount we have when we start the betting. The second argument is a string betResultsThe ith character of outcome will be either 'W' (win) or 'L' (lose), denoting the result of the ith round.
Your function should return the amount of money you will have after all the rounds are played. If at some point you don't have enough money in your account to cover the value of the bet, you must stop and return the sum you have at that point.

Sample Test Cases:

Input #00:
12
WWWWWWWW

Output #00:
20

Explanation:
The initial amount is 12, for every win, you gain 1 dollar.
There are totally 8 consecutive wins and no losses, hence total money gained = 12 + 8 = 20

Input #01:
15
LLLWLLLL

Output #01:
1

Explanation:
The initial amount is 15. As stated in the problem, the amount of bet doubles for every loss.
1st round - Loss: 15-1 = 14
2nd round - Loss: 14-2 = 12 (Bet doubles)
3rd round - Loss: 12-4 = 8
4th round - Win: 8 + 8 = 16
5th round - Loss:16-1 = 15 (Since the previous bet was a win, this bet has a value of 1 dollar)
6th round - Loss: 15-2 = 13
7th round - Loss: 13-4 = 9
8th round - Loss: 9-8 = 1

#include<iostream>
#include<string.h>
using namespace std;
int getFinalAmount(int init,char result[100])
{
    int amt=1;
    for(int i=0;i<strlen(result);i++)
    {
        if(result[i]=='W' || result[i]=='w')
        {
            if(init < amt)
            {
                return init;
            }
            init+=amt;
            amt=1;
        }
        else if(result[i]=='L' || result[i]=='l')
        {
            if(init < amt)
            {
                return init;
            }
            init-=amt;
            amt*=2;
        }
    }
    return init;
}
int main()
{
    int T;
    int win,lose,init;
    char result[100];
    cin>>T;
    while(T--)
    {
        cin>>init;
        cin>>result;
        cout<<getFinalAmount(init,result)<<endl;
    }
}
Input:
2
12
WWWWWWWW
15
LLLWLLLL

Output:
20
1

Number-to-Alphabet Decoding System

Problem
There is a coding system where all the letters in an Alphabet is coded into a number such as a-->1, b-->2,..., z-->26. Given an array of the integers, the program should output the number of possible letter arrangements in the decoded string.
C++ Program

#include<iostream>
using namespace std;
#define SIZE 4
int getCount(int A[SIZE],int s)
{
    if(s>=SIZE - 1)
    {
        return 1;
    }
    else
    {
        if(A[s]*10 + A[s+1] <= 26)
        {
            return getCount(A,s+1) + getCount(A,s+2);
        }
        else if(A[s] <= 26)
        {
            return getCount(A,s+1);
        }
        else
        {
            return 0;
        }
    }
}
int main()
{
    //int A[SIZE]={1,2,6,1,2,4};
    int A[SIZE]={1,1,2,3};
    int s=0;
    cout<<"Recursive: "<<getCount(A,s)<<endl;
    int a=1;
    int b=1;
    int ans=a;
    int n=SIZE;
    if(10*A[n-2]+A[n-1] <= 26)
    {
        a=2;
    }
    for(int i=n-3; i>=0; i--)
    {
        if(10*A[i]+A[i+1] <= 26)
        {
            ans=a+b;
            b=a;
            a=ans;
        }
        else
        {
            ans=a;
            b=a;
        }
    }
    cout<<"Dynamic Programming: "<<ans<<endl;
}
Output
Recursive: 5
Dynamic Programming: 5

Process returned 0 (0x0)   execution time : 0.018 s
Press any key to continue.

C++ program for jumps problem

Given an array of positive numbers, find the number of ways to reach the end of the array in minimum number of steps where the value at each index represents the maximum number of steps one can move.
Sample Input:
The first line contains a number n, the number of elements in the array. The second line contains n space separated numbers.
11
1 3 5 8 9 2 6 7 6 8 9
Sample Output
Output should contain n space separated numbers, each represents the number of ways at that index.
2 2 4 1 1 2 1 1 1 1 0

#include<iostream>
using namespace std;
int main()
{
    int n,A[100];
    cin>>n;
    int max=-9999999;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        if(A[i]>max)
        {
            max=A[i];
        }
    }
    //cout<<max<<endl;
    cout<<"The given array is:\n";
    for(int i=0;i<n;i++)
    {
        cout<<A[i]<<" ";
    }
    cout<<endl;
    int B[100]={0};
    for(int i=0;i<n-1;i++)
    {
        B[i]=A[i];
    }
    for(int i=n-2;i>=0;i--)
    {
        if(i+A[i] >= n-1)
        {
            B[i]=1;
        }
        else
        {
            int min=max;
            bool inside = false;
            for(int j=i+A[i];j>i;j--)
            {
                if(B[j]!=0 && B[j]<=min)
                {
                    min=B[j];
                    inside = true;
                }
            }
            if(inside)
            {
                B[i]=min+1;
            }
        }
    }
    cout<<"The distance array is:\n";
    for(int i=0;i<n;i++)
    {
        cout<<B[i]<<" ";
    }
    cout<<endl;
    int num[100]={0};
    for(int i=n-2;i>=0;i--)
    {
        if(B[i]==1)
        {
            num[i]=B[i];
        }
        else
        {
            for(int j=1;i+j<n && j<=A[i];j++)
            {
                if(B[i+j]==B[i]-1)
                {
                    //cout<<i<<" "<<B[i]<<" "<<j<<endl;
                    num[i]+=num[i+j];
                }
            }
        }
    }
    cout<<"Number of ways:\n";
    for(int i=0;i<n;i++)
    {
        cout<<num[i]<<" ";
    }
    cout<<endl;
}
11
1 3 5 8 9 2 6 7 6 8 9
The given array is:
1 3 5 8 9 2 6 7 6 8 9
The distance array is:
3 2 2 1 1 2 1 1 1 1 0
Number of ways:
2 2 4 1 1 2 1 1 1 1 0

C++ program to find all the possible interleavings of two input strings

#include<iostream>
#include<string.h>
#include<map>
using namespace std;
map<string,bool> myMap;
void generateInterleaved(char A[100],char B[100],char out[200],int start1,int start2)
{
    if(strlen(out)==strlen(A)+strlen(B))
    {
        if(myMap.find(out) == myMap.end())
        {
            myMap[out]=true;
        }
        return;
    }
    else
    {
        if(start1<strlen(A))
        {
            out[strlen(out)]=A[start1];
            generateInterleaved(A,B,out,start1+1,start2);
            out[strlen(out)-1]=0;
        }
        if(start2<strlen(B))
        {
            out[strlen(out)]=B[start2];
            generateInterleaved(A,B,out,start1,start2+1);
            out[strlen(out)-1]=0;
        }
    }
}
int main()
{
    char A[100],B[100],C[100];
    bool isInterleaved(char[],char[],char[]);
    cin>>A>>B>>C;
    bool result=isInterleaved(A,B,C);
    if(result==true)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    char out[200]={0};
    cout<<"The possible interleavings are:\n";
    generateInterleaved(A,B,out,0,0);
    for(map<string,bool>::iterator it = myMap.begin();it != myMap.end(); ++it)
    {
        cout<<it->first<<endl;
    }
}
bool isInterleaved(char A[100],char B[100],char C[100])
{
    int j=0,k=0;
    for(int i=0;i<strlen(C);i++)
    {
        if(j<strlen(A) && C[i]==A[j])
        {
            j++;
        }
        else if(k<strlen(B) && C[i]==B[k])
        {
            k++;
        }
    }
    if(j==strlen(A) && k==strlen(B))
    {
        return true;
    }
    else
    {
        return false;
    }
}
Input:
ab
cd
Output:
ab
cd
abcd
YES
The possible interleavings are:
abcd
acbd
acdb
cabd
cadb
cdab

Find the Largest Sum Path from root to leaf in a binary tree

#include<iostream>
#define SMALL -999999
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
 struct node* parent;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 new_node->parent=NULL;
 return new_node;
}
void parentfinder(node *root,node *parent)
{
    if(root)
    {
        root->parent=parent;
        parent=root;
        parentfinder(root->left,parent);
        parentfinder(root->right,parent);
    }
    return;
}
int height(struct node* root)
{
 if(root==NULL)
 {
  return 0;
 }
 else
 {
  int lheight=1+height(root->left);
  int rheight=1+height(root->right);
  return lheight>rheight?lheight:rheight;
 }
}
void levelorderprint(struct node* root,int level)
{
 if(root && level==0)
 {
  cout<<root->data<<"->";
  if(root->parent)
  {
      cout<<root->parent->data<<endl;
  }
 }
 else if(root)
 {
  levelorderprint(root->left,level-1);
  levelorderprint(root->right,level-1);
 }
}
void levelorder(struct node* root)
{
 int h=height(root);
 for(int i=0;i<h;i++)
 {
  levelorderprint(root,i);
  cout<<endl;
 }
}
struct node** summer(node *root,node **maximum,node *parent)
{
    if(root)
    {
        if(parent)
        {
            root->data=root->data+parent->data;
            if((*maximum)->data<root->data)
            {
                *maximum=root;
            }
        }
        parent=root;
        summer(root->left,maximum,parent);
        summer(root->right,maximum,parent);
    }
    return maximum;
}
int searchformax(node *root,node **max,bool *found,int A[100])
{
    static int i=0;
    if(root)
    {
        if(root==*max)
        {
            *found=true;
        }
        if(!(*found))
        {
            searchformax(root->left,max,found,A);
            if(!(*found))
            {
                searchformax(root->right,max,found,A);
            }
        }
        if(*found)
        {
            A[i]=root->data;
            i++;
        }
    }
    return i;
}
int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(-6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 parentfinder(root,NULL);
 levelorder(root);
 node *ptr=new struct node;
 ptr->data=SMALL;
 node **max=&ptr;
 max = summer(root,max,NULL);
 bool var=false;
 bool *found = &var;
 int A[100];
 int count=searchformax(root,max,found,A);
 for(int i=0;i<count-1;i++)
 {
     A[i]=A[i]-A[i+1];
 }
 cout<<"The path is:"<<endl;
 while(count--)
 {
     cout<<A[count]<<endl;
 }
}
Output:
1->
2->1
3->1

5->2
4->2
7->3
-6->3

8->-6
10->-6

The maximum sum path is:
1
3
7