Inorder Successor of BST

Problem

Concept

We can find the next inorder successor by performing an inorder traversal. But that is not an efficient way. Why? Because we are not using any properties of the BST to find out what is the next inorder successor.

We need to understand where the successor could appear if you want to use BST properties.

Using BST properties, if we want to find the inorder successor

Algorithm

Solution

Time Complexity:

n -> Number of nodes in BST

• Best Case: O(log n)

• Worse Case: O(n), skewed BST

Space Complexity: `O(1)`

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        /*
        n -> Number of nodes in BST
        Time Complexity:
            * Best Case: O(log n)
            * Worse Case: O(n), skewed BST
        Space Complexity: O(1)
        */
        TreeNode successor = null;

        while(root!=null) {
            // If search value is greater than or equal to root value
            // The possible successor could be on right subtree
            // So traverse to right sub tree
            if(p.val >= root.val) {
                root = root.right;
            } 
            // If search value is lesser than root value
            // then successor must lie on left sub tree and the current 
            // node could also be a possible inorder successor
            else if(p.val < root.val){
                successor = root;
                root = root.left;
            }
        } 
        return successor;  
    }
}