racseism
BAN USERint Distance(node *tree, int data)
{
// Keep in mind this is bst
if(tree == null) return -infinity;
if(tree->data == data) return 1;
if(tree->data > data)
{
return(1+Distance(tree->left,data));
}
else
{
return(1+Distance(tree->right,data));
}
}
int ShortestDistanceBetweenNodes(node *tree, node *node1, node *node2)
{
if(tree == null) return -1;
else if (node1 == null || node2 == null) return -1;
else if (node1->data == node2->data) return 0;
int min = Min(node1->data, node2->data);
int max = Max(node1->data, node2->data);
if(node->data > max)
{
return(ShortestDistanceBetweenNodes(node->left, node1, node2));
}
else if (node->data < min)
{
return(ShortestDistanceBetweenNodes(node->right, node1, node2));
}
else
{
if(node->data == min)
{
return(Distance(node->right,max));
}
else if (node->data == max)
{
return(Distance(node->left, min));
}
else
{
return(Distance(node->left,min) + Distance(node->right,max));
}
}
}
I have commented some part - you can fix the commented part in the same way
sing std::stack;
using std::string;
template<typename T>class Myqueue
{
stack<T> s1,s2;
public:
Myqueue(){
//s1=new stack<T>(); // Here no no need to use new
//s2=new stack<T>(); // Here no need to use new automatically the empty stack would would be created.
}
int size()
{
return s1.size()+s2.size();
}
void add(T value)
{
s1.push(value);
}
/*T peek()
{
if(!s2.empty())
return s2.peek();
while(!s1.empty())
s2.push(s1.pop());
return s2.peek();
}*/
T remove()
{
T returnValue;
if(!s2.empty())
{
returnValue = s2.top();
s2.pop();
}
else
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
if(!s2.empty())
{
returnValue = s2.top();
s2.pop();
}
}
return returnValue; // This is also not valid as when s2 is empty then it will fail as they would not be able to convert void to string
}
};
int CompilationErrorCheck()
{
Myqueue<string> str;
/*str.Myqueue();*/
string str1;
str.add("devesh");
str.add("pankaj");
std::cout<<"CurrenttopValue "<<str.remove()<<"\n";
//str1=str.peek();
return 0;
}
I have commented some part - you can fix the commented part in the same way
sing std::stack;
using std::string;
template<typename T>class Myqueue
{
stack<T> s1,s2;
public:
Myqueue(){
//s1=new stack<T>(); // Here no no need to use new
//s2=new stack<T>(); // Here no need to use new automatically the empty stack would would be created.
}
int size()
{
return s1.size()+s2.size();
}
void add(T value)
{
s1.push(value);
}
/*T peek()
{
if(!s2.empty())
return s2.peek();
while(!s1.empty())
s2.push(s1.pop());
return s2.peek();
}*/
T remove()
{
T returnValue;
if(!s2.empty())
{
returnValue = s2.top();
s2.pop();
}
else
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
if(!s2.empty())
{
returnValue = s2.top();
s2.pop();
}
}
return returnValue; // This is also not valid as when s2 is empty then it will fail as they would not be able to convert void to string
}
};
int CompilationErrorCheck()
{
Myqueue<string> str;
/*str.Myqueue();*/
string str1;
str.add("devesh");
str.add("pankaj");
std::cout<<"CurrenttopValue "<<str.remove()<<"\n";
//str1=str.peek();
return 0;
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
void PrintAllSubstring(char *input, int stIndex, int endIndex, char *output, int outlen)
{
if(stIndex > endIndex)
{
if(outlen != 0)
{
std::cout<<"\n";
for(int index = 0; index < outlen; index++)
{
std::cout<<output[index]<<" ";
}
}
return;
}
output[outlen] = input[stIndex];
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen + 1);
PrintAllSubstring(input, stIndex + 1, endIndex, output, outlen);
}
@Manan - What is your terminating condition in recursion so that you can print the tree at that time....
I have worried ..here not about recursions..but I am not able to find the point/conditions when I should print the tree..
I think you understood my confusion...
void AmazonGlassProblem(int maxlitres, int numberofLevel, int glassCapacity)
{
float glasses[1000] = {0};
int glassInALevel = 1;
int currentLevel = 0;
bool isNextLevelRequired = true;
glasses[0] = maxlitres;
while(currentLevel < numberofLevel)
{
for(int indexInLevel = 1; indexInLevel <= currentLevel + 1; indexInLevel++)
{
int glassIndex = (currentLevel*(currentLevel + 1))/2;
if(glasses[glassIndex - 1+indexInLevel] > glassCapacity)
{
float remainCapacity = glasses[glassIndex - 1+indexInLevel] - glassCapacity;
int nextIndex = ((currentLevel+1) * (currentLevel + 2))/2 + indexInLevel;
glasses[nextIndex -1] += remainCapacity/2;
glasses[nextIndex] += remainCapacity/2;
glasses[glassIndex - 1+indexInLevel] = glassCapacity;
}
}
currentLevel++;
}
for(int index =0 ; index < (numberofLevel *(numberofLevel + 1))/2; index++)
{
std::cout<<"\n Glass of "<<index<<" "<<glasses[index]<<" "<<"litres";
}
}
void InputForMaxLitresProblem()
{
AmazonGlassProblem(10,5,1);
}
Actually -- The question is , we do not have to traverse all the leaf nodes if the previous leaf nodes ..does not match..
- racseism February 17, 2012so while you are enqueing ..you are traversing all the nodes ...so I think your solution is not as per question