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,

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 peers are preparing the onsite interview less than one month, some of them complain my communication, I learn to challenge every peer to make sure that the peer learns something after the interview. I start to look for an algorithm to give them additional challenge. The recursive solution with a tricky base case is my first one, I have used the algorithm thrice. The peer with strong confidence may solve it in less than 10 minutes, otherwise I can learn how to give hints to help them.

Recursive solution

The algorithm is my first choice and I asked three peers to solve the algorithm as an additional test, all of them gave me good feedback. It is hard for them to solve in less than 10 minutes, none of them solves the problem before, and kind of overthinking the solution, using stack or think too much detail. So I decide to ask a code review for the algorithm as well, make sure that I understand correctly.

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 tried to use another hint on mock interview. The peer could not think using simple recursive solution, he kept busy thinking about inorder traversal using stack. I tried to use the hint: If the root node asks its right node to solve the same problem, or its left node to solve the same problem, when the root node does the work itself. So it is my design to let the root node be the successor. The base case is all you should care about. The peer also gave good feedback on this hint.

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.             
        /// </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);
            }
        }
    }
}
  • I had a mock interview 8:00 PM on Feb. 12, 2018, and then the peer shared with me his experience on Leetcode 776: Binary search tree split tree. I was asked to solve the problem. Actually it is so easy to figure out using the above binary search tree inorder successor recursive solution. I wrote one and here is the link: gist.github.com/jianminchen/5ce3f22292c62b26f82dbf5b59486ed3 – Jianmin Chen Feb 13 at 6:33

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.