import java.util.* ;
import java.lang.* ;
import java.io.* ;
class Ideone
{
static class Node
{
Node left, right;
Node
( Integer key
) { this .
key = key
; } }
{
Integer successor
= successor
( root, target
) ; if ( successor == specialKey)
return null ;
return successor;
}
{
if ( current == null )
return null ;
if ( target.equals ( current.key ) )
if ( current.right != null )
return leftMost( current.right ) .key ;
else
return specialKey;
else
if ( target < current.key )
{
Integer s
= successor
( current.
left , target
) ; if ( s == specialKey)
return current.key ;
else
return s;
}
else
return successor( current.right , target) ;
}
static Node leftMost( Node current)
{
while ( current.left != null )
current = current.left ;
return current;
}
static Node root;
public static void main
( String [ ] args
) {
// Constructs this tree:
// 6
// / \
// 2 7
// / \
// 1 4
// / \
// 3 5
root = new Node( 6 ) ;
root.left = new Node( 2 ) ;
root.left .left = new Node( 1 ) ;
root.left .right = new Node( 4 ) ;
root.left .right .left = new Node( 3 ) ;
root.left .right .right = new Node( 5 ) ;
root.right = new Node( 7 ) ;
for ( int i = 0 ; i <= 7 ; i++ )
System .
out .
println ( "Successor of " + i
+ " is " + successor
( i
) ) ; }
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUKewogICBzdGF0aWMgY2xhc3MgTm9kZQogICB7CiAgICAgIEludGVnZXIga2V5OwogICAgICBOb2RlIGxlZnQsIHJpZ2h0OwogICAgICBOb2RlKEludGVnZXIga2V5KSB7IHRoaXMua2V5ID0ga2V5OyB9CiAgIH0KICAgCiAgIHN0YXRpYyBJbnRlZ2VyIHNwZWNpYWxLZXkgPSBJbnRlZ2VyLk1BWF9WQUxVRTsKCiAgIHN0YXRpYyBJbnRlZ2VyIHN1Y2Nlc3NvcihJbnRlZ2VyIHRhcmdldCkKICAgewogICAgICBJbnRlZ2VyIHN1Y2Nlc3NvciA9IHN1Y2Nlc3Nvcihyb290LCB0YXJnZXQpOwogICAgICBpZiAoc3VjY2Vzc29yID09IHNwZWNpYWxLZXkpCiAgICAgICAgIHJldHVybiBudWxsOwogICAgICByZXR1cm4gc3VjY2Vzc29yOwogICB9CiAgIHN0YXRpYyBJbnRlZ2VyIHN1Y2Nlc3NvcihOb2RlIGN1cnJlbnQsIEludGVnZXIgdGFyZ2V0KQogICB7CiAgICAgIGlmIChjdXJyZW50ID09IG51bGwpCiAgICAgICAgIHJldHVybiBudWxsOwogICAgICBpZiAodGFyZ2V0LmVxdWFscyhjdXJyZW50LmtleSkpCiAgICAgICAgIGlmIChjdXJyZW50LnJpZ2h0ICE9IG51bGwpCiAgICAgICAgICAgIHJldHVybiBsZWZ0TW9zdChjdXJyZW50LnJpZ2h0KS5rZXk7CiAgICAgICAgIGVsc2UKICAgICAgICAgICAgcmV0dXJuIHNwZWNpYWxLZXk7CiAgICAgIGVsc2UKICAgICAgICAgaWYgKHRhcmdldCA8IGN1cnJlbnQua2V5KQogICAgICAgICB7CiAgICAgICAgICAgIEludGVnZXIgcyA9IHN1Y2Nlc3NvcihjdXJyZW50LmxlZnQsIHRhcmdldCk7CiAgICAgICAgICAgIGlmIChzID09IHNwZWNpYWxLZXkpCiAgICAgICAgICAgICAgIHJldHVybiBjdXJyZW50LmtleTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICByZXR1cm4gczsKICAgICAgICAgfQogICAgICAgICBlbHNlCiAgICAgICAgICAgIHJldHVybiBzdWNjZXNzb3IoY3VycmVudC5yaWdodCwgdGFyZ2V0KTsKICAgfQoKICAgc3RhdGljIE5vZGUgbGVmdE1vc3QoTm9kZSBjdXJyZW50KQogICB7CiAgICAgIHdoaWxlIChjdXJyZW50LmxlZnQgIT0gbnVsbCkKICAgICAgICAgY3VycmVudCA9IGN1cnJlbnQubGVmdDsKICAgICAgcmV0dXJuIGN1cnJlbnQ7CiAgIH0KICAgCiAgIHN0YXRpYyBOb2RlIHJvb3Q7CiAgIAogICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKQogICB7CiAgICAgIC8vIENvbnN0cnVjdHMgdGhpcyB0cmVlOgogICAgICAvLyAgICAgICAgIDYKICAgICAgLy8gICAgICAgIC8gXAogICAgICAvLyAgICAgICAyICAgNwogICAgICAvLyAgICAgIC8gXAogICAgICAvLyAgICAgMSAgIDQKICAgICAgLy8gICAgICAgIC8gXAogICAgICAvLyAgICAgICAzICAgNQogICAgICAKICAgICAgcm9vdCA9IG5ldyBOb2RlKDYpOwogICAgICByb290LmxlZnQgPSBuZXcgTm9kZSgyKTsKICAgICAgcm9vdC5sZWZ0LmxlZnQgPSBuZXcgTm9kZSgxKTsKICAgICAgcm9vdC5sZWZ0LnJpZ2h0ID0gbmV3IE5vZGUoNCk7CiAgICAgIHJvb3QubGVmdC5yaWdodC5sZWZ0ID0gbmV3IE5vZGUoMyk7CiAgICAgIHJvb3QubGVmdC5yaWdodC5yaWdodCA9IG5ldyBOb2RlKDUpOwogICAgICByb290LnJpZ2h0ID0gbmV3IE5vZGUoNyk7CiAgICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IDc7IGkrKykKICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJTdWNjZXNzb3Igb2YgIiArIGkgKyAiIGlzICIgKyBzdWNjZXNzb3IoaSkpOwogICB9Cn0=