Please help me with the code for the successor method. These are the steps I tho
ID: 3560399 • Letter: P
Question
Please help me with the code for the successor method.
These are the steps I thought of: if the value n = to root then it will return the minimum of the right tree.
if value is greater than root, then it will return the successor in the right tree
if value is less than root it will return the successor in the left tree.
The main method is done.
static class Tree
{
int data;
Tree left;
Tree right;
}
private static Integer min(Tree root)
{
if(root.left == null)
return root.data;
else
return min(root.left);
}
The method will return the successor of value n in tree root; the first bigger number than value n. If n is the maximum value in tree, then there won't be another successor. the method returns null.
public static Integer successor(Tree root, int n)
{
}
Explanation / Answer
Finding the successor node of a given node:
There are two cases here:
1. The node has a right subtree.
If the given node has a right subtree then by the BST property the next larger key must be in the right subtree. Since all keys in a right subtree are larger than the key of the given node, the successor must be the smallest of all those keys in the right subtree.
2. The node does not have a right subtree.
In this case we will have to look up the tree since that's the only place we might find the next larger key. There is no point looking at the left subtree as all keys in the left subtree are guaranteed to be smaller than the key in the given tree.
When we look up from the given node, there can be two cases: first, the current node is the left child of its parent. In this case the parent is the successor node. This is because the parent always comes next in inorder traversal if you are done with left subtree (rooted at the current node).
Second, the current node is the right child of the parent. This is an interesting case. In this case, as you keep going up the ancestor chain you encounter smaller values if you are going up but larger values if you are going right. The successor node will be the first node up the ancestor chain that you encounter on the right chain.
Here is the Java code to find the successor of a given node. This assumes a class TreeNode that represents nodes in the BST:
public static TreeNode findSuccessor(TreeNode node)
{
if (node == null)
return null;
if (node.getRight() != null)
return findMinimum(node.getRight());
TreeNode y = node.getParent();
TreeNode x = node;
while (y != null && x == y.getRight())
{
x = y;
y = y.getParent();
}
// Intuition: as we traverse left up the tree we traverse smaller values
// The first node on the right is the next larger number
return y;
}