Last active
August 23, 2020 06:12
-
-
Save gabhi/11388283 to your computer and use it in GitHub Desktop.
inorder successor and predecessor in a Binary Search Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/ | |
//With Parent node given | |
struct node * inOrderSuccessor(struct node *root, struct node *n) | |
{ | |
// step 1 of the above algorithm | |
if( n->right != NULL ) | |
return minValue(n->right); | |
// step 2 of the above algorithm | |
struct node *p = n->parent; | |
while(p != NULL && n == p->right) | |
{ | |
n = p; | |
p = p->parent; | |
} | |
return p; | |
} | |
//without parent node | |
struct node * inOrderSuccessor(struct node *root, struct node *n) | |
{ | |
// step 1 of the above algorithm | |
if( n->right != NULL ) | |
return minValue(n->right); | |
struct node *succ = NULL; | |
// Start from root and search for successor down the tree | |
while (root != NULL) | |
{ | |
if (n->data < root->data) | |
{ | |
succ = root; | |
root = root->left; | |
} | |
else if (n->data > root->data) | |
root = root->right; | |
else | |
break; | |
} | |
return succ; | |
} | |
public static TreeNode findPredecessor(TreeNode node) | |
{ | |
if (node == null) | |
return null; | |
if (node.getLeft() != null) | |
return findMaximum(node.getLeft()); | |
TreeNode parent = node.getParent(); | |
TreeNode y = parent; | |
TreeNode x = node; | |
while (y != null && x == y.getLeft()) | |
{ | |
x = y; | |
y = y.getParent(); | |
} | |
return y; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Unfortunately, this doesn't seem like
java