spiffinme
BAN USER//Check the tree inorder and see if that is in ascending order
//Helper function for easy use. Sets up a buffer that is needed by the code
bool bst(Node *p)
{
int buf_min = numeric_limits<int>::min(); // minimum value held in int
return(bst_full(p, buf_min));
}
//Code that checks if the tree is a BST
bool bst_full(Node *p, int& buf_min)
{
if(!p) return true;
if(bst_full(p->left,buf_min))
{
if(p->data >= buf_min)
{
buf_min = p->data;
return bst_full(p->right,buf_min);
}
else return false;
}
else return false;
}
o(1) space and O(n) time complexity.
Every node visited once.
#include<iostream>
#include <limits.h>
using namespace std;
/* A binary tree node has
data,
pointer to left child
pointer to right child
*/
struct node
{
int data;
struct node* left;
struct node* right;
};
typedef struct node Node;
/* Function that allocates a new node with the
given data and sets up left and right pointers as NULL value.
*/
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
//------------------------------------code here----------------------
//Function that checks if given tree is a BST. Declared here.
bool isBST_Full(Node *p, int& prev);
//Helper function for easy use. Sets up a buffer that is needed by the code
bool isBST(Node *p)
{
int prev = numeric_limits<int>::min(); // minimum value held in int
return(isBST_Full(p, prev));
}
bool isBST_Full(Node *p, int& prev)
{
if(!p) return true;
if(isBST_Full(p->left,prev))
{
if(p->data>=prev)
{
prev = p->data;
return(isBST_Full(p->right,prev));
}
else return false;
}
else return false;
}
//----------------------------------------------------------------------------
int main()
{
struct node *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
root->right->right = newNode(8);
if(isBST(root))
printf("Is BST");
else
printf("Not a BST");
return 0;
}
flag == 1 is the right code
As seen in this output... the object P now holds the values 30 40
Before Pointer p1: 1020
------>Before Object P : 1020
-In written function
-Switch Values physically
After Pointer p1: 3040
------>After Object P : 3040
flag ==2 does nothing. As you said its just passed by value and thrown out
i left it in so i could see the outputs and compare
Before Pointer p1: 1020
------------>Before Object P : 1020
-In written function
-Does nothing in code
After Pointer p1: 1020
------------->After Object P : 1020
What worked for me
1.Explicitly calling swap using swap((void *)a,(void *)b);
2.Using memcpy to physically change contents of the objects.
Code below. Tested on c++ in codepad.com
//Swapping objects using void pointers
#include <iostream>
#include <stdlib.h>
using namespace std;
struct node
{
int a,b;
};
typedef struct node Node;
void swap(void *a, void *b, int flag=1)
{
cout<<"\n-In written function";
//CORRECT CODE
if (flag==1)
{
//Physically replaces data while pointers point to same location
cout<<"\n-Switch Values physically";
void *temp = new Node;
memcpy(temp,a,sizeof(Node));
memcpy(a,b,sizeof(Node));
memcpy(b,temp,sizeof(Node));
}
//INCORRECT CODE
else if (flag==2)
{
//Exchanges what pointers are pointing to
cout<<"\n-Does nothing in code";
void *temp;
temp =a;
a=b;
b=temp;
}
else
{
cout<<"\n-Wrong choice nothing done";
}
}
int main()
{
Node P,Q;
Node *p1 = &P;
Node *p2 = &Q;
p1->a = 10; p1->b = 20;
p2->a = 30; p2->b = 40;
cout<<"\n Before Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout<<"\n Before Objects P : "<<P.a<<P.b;
cout<<"\n In built swap called. Not the one we wrote. Changes what the pointers point to. Uses template to accomplish. Wise.";
swap(p1,p2); //Calls build in function from std. No String in output.
cout<<"\n After Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout<<"\n After Object P : "<<P.a<<P.b;
swap(p1,p2); //swaps back
//Correct Run
cout<<"\n\n Before Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout<< "\n Before Object P : "<<P.a<<P.b;
swap((void *)p1,(void *)p2,1); //Explicit call to our function
cout<<"\n After Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout<<"\n After Object P : "<<P.a<<P.b;
swap((void *)p1,(void *)p2,1); //swaps back
//Incorrect Run
cout<<"\n\n Before Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout <<"\n Before Object P : "<<P.a<<P.b;
swap((void *)p1,(void *)p2,2); //Explicit call to our function
cout<<"\n After Pointer p1: "<<((Node *)p1)->a<<((Node *)p1)->b;
cout<<"\n After Object P : "<<P.a<<P.b;
return 0;
}
Output
//IN BUILT SWAP FUNCTION CALLED INSTEAD OF THE ONE ABOVE
Before Pointer p1: 1020
Before Objects P : 1020
In built swap called. Not the one we wrote. Changes what the pointers point to. Uses template to accomplish.Wise.
After Pointer p1: 3040
After Object P : 1020
//CORRECT RESULT
Before Pointer p1: 1020
Before Object P : 1020
-In written function
-Switch Values physically
After Pointer p1: 3040
After Object P : 3040
//SWAP BACK IGNORE
-In written function
-Switch Values physically
//INCORRECT RESULT
Before Pointer p1: 1020
Before Object P : 1020
-In written function
-Does nothing in code
After Pointer p1: 1020
After Object P : 1020
Do let me know if you have any comments.
#include<iostream>
#include<math.h>
/*Assumptions:
char string given in format -- char []
number may be any positive integer
always single alphabet, anything other than number is considered alphabet
all inputs correct. E.g. no incorrect inputs like 22a2 or abc4-->written as a1b1c4
*/
using namespace std;
void fix(char *all_s, char *all_e, char *in_s, char *in_e)
/*
all_s,all_e : mark the start and ending of complete space under consideration
in_s,in_e : mark where to start reading from when running backwards
Alg:
Move backwards
-Get num
Mark position Pos from where to start copying later, save char to copy
Recursively call itself with new space under consideration and where to start reading input
Upon return, from Pos,copy saved character num times
*/
{
if((in_s>=in_e)||(all_s>=all_e)) return;
//Moving backwards get num
int num = 0, count = -1;
while(*in_e>='0'&&*in_e<='9')
{
count++;
num = (( *in_e- '0' ) * int(pow((double)10,(double)count))) + num;
in_e--;
}
char *pos = all_e-num+1;
char c = *in_e;
fix(all_s,all_e-num,in_s,in_e-1);
for(int i = 0; i<num; i++)
{
*pos = c;
pos++;
}
}
int main()
{
char str[] = "a2b4c5---------------------------------------------------";
cout<<"Input : "<<str;
//call properly
fix(&str[0],&str[10],&str[0],&str[5]);
cout<<"\nRESULT : "<<str;
char str2[] = "a1b1c4---------------------------------------------------";
cout<<"\nInput : "<<str2;
//call properly
fix(&str2[0],&str2[5],&str2[0],&str2[5]);
cout<<"\nRESULT : "<<str2;
char str3[] = "a11b11c5---------------------------------------------------";
cout<<"\nInput : "<<str3;
//call properly
fix(&str3[0],&str3[11+11+5-1],&str3[0],&str3[7]);
cout<<"\nRESULT : "<<str3;
return 0;
}
how about this?
- spiffinme April 15, 2013Check for a balanced tree. if not balanced it?? or say cant do in log in
IF it is a balanced tree
Use log N steps to reach the minimum value where N is number of elements
and iteratively find successors till we get the nth smallest element.
This will take log N steps, n times
so O(logN) + O(nlogN) where n is a constant = O(logN)