Algorithm:
1.Find The Minimum value in BSt if givfen Node has the same value we are done as
the minimum value in BST is left most leaf & can't have any predecessor :)
2.Check if node->Left is leaf or not if yes then node->left is our answer
3.if n is right child then its parent will be inorder predecessor
4.else eif all aobe case fail then inorder predecessor be maximum value in left
subtree of given node N.
This Algo will take O(logn) Time in Avg.Case & O(N) time in Worst Case Skew Tree :)
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};
/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* minValue(struct node* node);
int isLeaf(struct node* root)
{
if(root->left==NULL && root->right==NULL)
return 1;
return 0;
}
/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* maxValue(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right!= NULL) {
current = current->right;
}
return current;
}
struct node* inOrderPredecessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm
if(n==minValue(root))
{
printf("No Inorder Predecessor Possible");
return NULL;
}
//2nd step of above algo
//if(n->left->data==maxValue(root))
//return n->left->data;
if(isLeaf(n->left))
return n->left;
//3rd step if n is right children of parent
struct node *p =n->parent;
if(n == p->right)
return p;
// step 4 of the above algorithm if all above not satisfied then predecessor exist in right
return maxValue(n->left);
}
/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* minValue(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->right;
}
return current;
}
/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}
/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
struct node *temp;
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
{
temp = insert(node->left, data);
node->left = temp;
temp->parent= node;
}
else
{
temp = insert(node->right, data);
node->right = temp;
temp->parent = node;
}
/* return the (unchanged) node pointer */
return node;
}
}
/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *t1,*t2,*t3,*t4, *s1,*s2,*s3,*s4 ;
//creating the tree given in the above diagram
root = insert(root, 6);
root = insert(root, 4);
root = insert(root, 13);
root = insert(root, 2);
root = insert(root, 5);
root = insert(root, 11);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 8);
root = insert(root, 9);
root = insert(root, 12);
root = insert(root, 10);
t3 = root->right->left;
/*t1 = root->left->left;
t2 = root->left->right;
t3 = root->right->left;
t4 = root->right->right;
s1 = inOrderPredecessor(root, t1);
if(s1 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t1->data, s1->data);
s2 = inOrderPredecessor(root, t2);
if(s2 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t2->data, s2->data);
s3 = inOrderPredecessor(root, t3);
if(s3 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t3->data, s3->data);
s4 = inOrderPredecessor(root, t4);
if(s4 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t4->data, s4->data);
*/
s3 = inOrderPredecessor(root, t3);
if(s3 != NULL)
printf("\n Inorder Predecessor of %d is %d ", t3->data, s3->data);
getchar();
return 0;
}
its due to insertion take o(nlogn)
Time Complexity O(NlogN) findPredecessor Will Take O(logn) in Avg. & O(N) in worst
Space Complexity O(1)
Run Here https://ideone.com/BJCtg
2nd Method Without Using Parent Pointer (Optimize Version)
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};
/* Given a non-empty binary search tree, return the maximumdata
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node* maxValue(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right!= NULL) {
current = current->right;
}
return current;
}
/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}
struct node * inOrderPredecessor(struct node *root, struct node *n)
{
if( n->left != NULL )
return maxValue(n->left);
struct node *pred=NULL;
while(root)
{
if(n->data < root->data)
root=root->left;
else if(n->data > root->data)
{
pred=root;
root=root->right;
}
else
break;
}
return pred;
}
/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
}
/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;
//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;
succ = inOrderPredecessor(root, temp);
if(succ != NULL)
printf("\n Inorder Predecessorof %d is %d ", temp->data, succ->data);
getchar();
return 0;
}
Feel Free to Test it for More Test Cases & do notify me if it will fail :)
its due to insertion take o(nlogn)
Time Complexity O(NlogN) findPredecessor Will Take O(logn) in Avg. & O(N) in worst
Space Complexity O(1)
Run Here http://ideone.com/eKtet
No comments :
Post a Comment