**Problem statement**

Given the root node and a node in the binary search tree, find the inorder successor of the given node.

Here is the example of binary search tree,

Given the node with value 14, its inorder successor is 20; given the node with value 25, its inorder successor is null. given the node with value 9, its inorder successor is 11.

**My introduction of the algorithm**

I just started to work on another round of mock interview last few days, but I chose myself as an advanced level interviewer the first time, a few of my peers are senior level programmers and one of them really likes coding over 30 years. I have to find some algorithms to help myself as an interviewer, and help them to prepare most important interview in less than one month, usually Google/ Facebook onsite interview.

**Recursive solution**

The algorithm is my first choice and I applied to two peers, both of them gave me good feedback. Because it is hard for them to solve in less than 10 minutes. So I decide to ask a code review for the algorithm, help myself to prepare better as a mock interviewer.

Here are hints I prepare to give and help peers to solve the problem in less than 10 minutes.

My first question is “**If you try to write some code as simple as possible, and also try to give a partial solution. What is most easiest thing to do?**”

What if the given node is the root node? It is simple to figure out, go to root node’s right child and call the recursive function.

And the next hint is how to relax the condition, when to call node’s right child and let it solve the problem. The root node’s value is not bigger than the given node’s value, so the successor node’s value should be in the right subtree.

Next question is “**when the root node is the successor**“. We need to land the successor on one of nodes, which is the base case. The best candidate is the root node. For example, shown in the graph of problem statement, the binary search tree with root node value 20, given node with value 14, the successor is root node with value 20. If the root node’s value is bigger than give node’s value 14, the root node can be either the successor or the node located after the successor.

I choose the algorithm based on Leetcode discussion here. I find that the algorithm is very good to test the candidate on recursive solution problem solving. It takes time to solve the problem, but if you decide to solve the partial of the solution, start something as simple as possible first, you will end up with a surprise. That is my coaching tip, to help the peer to build confidence, **aim the smallest target first, write the simplest code as possible**.

Here is my C# code and please help me review the code.

`using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BinarySearchTreeInOrderSuccessor { /// <summary> /// The algorith is written for my mock interview to test the candidate recursive solution. /// </summary> class Program { internal class TreeNode { public int Value { get; set; } public TreeNode Left { get; set; } public TreeNode Right { get; set; } public TreeNode(int number) { Value = number; } } static void Main(string[] args) { RunTestcase(); } public static void RunTestcase() { // work on root node var node20 = new TreeNode(20); // work on level 1 var node9 = new TreeNode(9); var node25 = new TreeNode(25); // work on connection from root node to its children node20.Left = node9; node20.Right = node25; // work on level 2 var node5 = new TreeNode(5); var node12 = new TreeNode(12); // work on connection from level 1's nodes to their children node9.Left = node5; node9.Right = node12; // work on level 3 var node11 = new TreeNode(11); var node14 = new TreeNode(14); // work on connection from level 2's nodes to their children node12.Left = node11; node12.Right = node14; var successor1 = FindBinarySearchTreeInOrderSuccessor(node20, node14); Debug.Assert(successor1 == node20); var successor2 = FindBinarySearchTreeInOrderSuccessor(node20, node9); Debug.Assert(successor2 == node11); var successor3 = FindBinarySearchTreeInOrderSuccessor(node20, node25); Debug.Assert(successor3 == null); } /// <summary> /// Find binary search tree inorder successor /// Customize the code to make base case easy to be identified and also /// follow the /// </summary> /// <param name="root"></param> /// <param name="givenNode"></param> /// <returns></returns> public static TreeNode FindBinarySearchTreeInOrderSuccessor(TreeNode root, TreeNode givenNode) { if (root == null) { return null; } var searchLeftSubtree = root.Value > givenNode.Value; // base case - work on root node var possibleSuccessor = searchLeftSubtree? root : null; if (searchLeftSubtree) { var successor = FindBinarySearchTreeInOrderSuccessor(root.Left, givenNode); return (successor != null) ? successor : possibleSuccessor; } else { return FindBinarySearchTreeInOrderSuccessor(root.Right, givenNode); } } } } `