In-order Successor of Binary Search Tree

Statement

Write a method to find the in-order successor of a BST node with a given value. Return -1 if the node with the given value does not exist.

The in-order successor of a node in a BST is the node with the smallest key greater than the key of the current node. This is the same as the next node in an in-order traversal of the BST.

Example

Consider the following BST:

In the table below, we can see the in-order successor for some of the nodes in this tree:

Node	In-order Successor
25	50
100	125
350	NULL

Note: The in-order successor of 350 is NULL since that’s the last node.

Sample input

The input list below represents the level-order traversal of the binary search tree, while the value that follows represents the node whose in-order successor we need to find:

[100, 50, 200, 25, 75, 125, 350], 50    

Expected output

75

Try it yourself

Note: The binary tree node’s class has members left and right ...