[Microsoft Question] Inorder Successor in Binary Search Tree

Problem: Given a binary search tree and a node in it, return the in-order successor of that node in the binary search tree. If the given node has no in-order successor in the tree, return null.

The successor of a node is the node with the smallest value greater than value of the given input node.

Example:

Input: Above tree, input = 6
Output: 8

Approach: We can use the similar approach which we used which we used to set the inorder successor of every node in Binary tree but that will take linear time as we are not using Binary Search Tree's property in this approach.

Let's make the solution efficient by using the BST's property. We can do preorder traversal here. There can be two conditions at every node:

1. curr_node.Value <= input.Value: In this case we just discard the left subtree of the curr_node.
2. curr_node.Value > input.Value: In this case we can discard the right subtree of curr_node, but if we see curr_node can also be a candidate of being a inorder successor of the input node.

With this understanding, look at the implementation to understand the whole solution.

Implementation in C#:

    public BinaryTreeNode InorderSuccessor(BinaryTreeNode input) 

    {

        if (this.Root == null)

        {

            return null;

        }

        BinaryTreeNode successor = null;

        BinaryTreeNode node = this.Root;

        while (node != null)

        {

            if (node.Value <= input.Value)

            {

                node = node.RightNode;

            }

            else

            {

                successor = node;

                node = node.LeftNode;

            }

        }

        return successor;

    }

Complexity: O(logn)