285. Inorder Successor in BST

Description

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

The successor of a node p is the node with the smallest key greater than p.val.

Constraints

• The number of nodes in the tree is in the range [1, 104].

• -105 <= Node.val <= 105

• All Nodes will have unique values.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: root = [2, 1, 3], p = 1

Output: 2

Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2

Input: root = [5, 3, 6, 2, 4, null, null, 1], p = 6

Output: null

Explanation: There is no in-order successor of the current node, so the answer is null.

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
}

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null || p == null) {
            return null;
        }
        
        if(root == p) {
            return root.right;
        }
        
        Stack<TreeNode> stack = new Stack();
        TreeNode curr = root;
        
        while(!stack.isEmpty() || curr != null) {
            while(curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode temp = stack.pop();
            curr = temp.right;
            
            if(temp == p) {
                if(temp.right != null) {
                    TreeNode m = temp.right;
                    while(m.left != null) {
                        m = m.left;
                    }
                    return m;
                } else if(!stack.isEmpty()) {
                    return stack.pop();
                }
            }
        }
        
        return null;
    }
}

Solution 2

/**
 * Time complexity : O(N) since we might end up encountering a skewed tree 
 *    and in that case, we will just be discarding one node at a time. 
 *    For a balanced binary-search tree, however, the time complexity 
 *    will be O(logN) which is what we usually find in practice.
 * Space complexity : O(1)
 */
 
 class Solution {
    
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        
        TreeNode successor = null;
        
        while (root != null) {
            
            if (p.val >= root.val) {
                root = root.right;
            } else {
                successor = root;
                root = root.left;
            }
        }
        
        return successor;
    }
}

Follow up