Inorder Successor in BST

In this challenge, we'll learn about Binary Search Trees and find the Inorder Successor of a given node. Imagine climbing a tree where each node has a left and right child. If you stand on one node, the Inorder Successor is the node you would visit next in an in-order traversal (left-root-right).

Let's play with a Binary Search Tree (BST) using numbers:

When you traverse a BST in-order, you visit the nodes in increasing order. For any node, the inorder successor is the smallest node larger than itself located to the right of it.

For example:

Input tree:
     5
    / \
   3   8
  / \   \
 2   4   9

If the target node is `3`, the inorder successor is `4`.
If the target node is `5`, the inorder successor is `8`.

Your task is to implement a function inorder_successor_in_bst that returns the value of the inorder successor given the root of a BST and a target node. If the target node has no successor (e.g., it's the largest element), return None.

Let's look at some examples:

# Create a simple Binary Search Tree for testing
root = TreeNode(5)
node3 = TreeNode(3)
node4 = TreeNode(4)
node8 = TreeNode(8)
node2 = TreeNode(2)
node9 = TreeNode(9)
root.left = node3
root.right = node8
node3.left = node2
node3.right = node4
node8.right = node9

print(inorder_successor_in_bst(root, node3)) # Output: 4
print(inorder_successor_in_bst(root, node5)) # Output: 8
print(inorder_successor_in_bst(root, node9)) # Output: None

How the tests work

Each test gives the tree as nested val, left and right entries, plus the value of the target node. The tree is built for you, and your function receives the real target node.