Skip to content

Instantly share code, notes, and snippets.

@gabhi
Last active August 23, 2020 06:12
Show Gist options
  • Save gabhi/11388283 to your computer and use it in GitHub Desktop.
Save gabhi/11388283 to your computer and use it in GitHub Desktop.
inorder successor and predecessor in a Binary Search Tree
//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;
}
@wonhyukchoi
Copy link

Unfortunately, this doesn't seem like java

@gabhi
Copy link
Author

gabhi commented Aug 23, 2020

Yes only last method is java @wonhyukchoi

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment