Problem Statement

Given a binary search tree and the value of a certain node, find the next node in the inorder sequence after the given node.

Solution Explanation

The important information here is that the tree is a binary search tree and we need to find the next node in the inorder sequence. We can deduce the following things:

• As we know in a binary search tree, each node in the left sub tree is lesser than the node value and each node in the right subtree is larger than the node value.
• Inorder traversal of a BST gives you the sorted list of values in the given tree.

Using this information, we can design our logic such that, we set a flag when we encounter the given value in the Inorder traversal and in each recursion call, we check if the flag is true, if it is, then we set the current node's value to the result.

We can use a helper which has the root node, input node value, boolean flag and the result list. It will look like this,

public static void inOrderHelper(Node root, int k,boolean isKFound,List<Integer> result){}

We pass isKFound as false initially, change its value when we encounter 'k' in the inorder traversal and set the value to result when the flag is true.

Below is the full java implementation of Find Inorder Successor in a Binary Search Tree,

public class FullBinarySearchTreeImpl {

	public static void main(String[] args) {
		Node root = new Node(10);
		insertVal(15, root);
		insertVal(7, root);
		insertVal(87, root);
		insertVal(36, root);
		insertVal(55, root);
		printBST(root);
		findInorderSuccessor(root, 15);
	}

	public static void insertVal(int newVal, Node root) {

		if (root == null) {
			return;
		}
		if (root.val < newVal) {
			if (root.right != null)
				insertVal(newVal, root.right);
			else {
				Node temp = new Node(newVal);
				root.right = temp;
			}
		} else if (root.val > newVal) {
			if (root.left != null)
				insertVal(newVal, root.left);
			else {
				Node temp = new Node(newVal);
				root.left = temp;
			}
		}

	}

	public static void printBST(Node root) {
		if (root == null)
			return;
		System.out.println(root.val + ",");
		printBST(root.left);
		printBST(root.right);
	}

	public static int findInorderSuccessor(Node root, int k) {
		List<Integer> res = new ArrayList<>();
		inOrderHelper(root, k, false, res);
		System.out.println("result is " + res.get(0));
		return res.get(0);
	}

	public static void inOrderHelper(Node root, int k, boolean isKFound, List<Integer> result) {
		if (root == null)
			return;
		inOrderHelper(root.left, k, isKFound, result);
		if (isKFound)
			result.add(root.val);
		if (root.val == k)
			isKFound = true;
		inOrderHelper(root.right, k, isKFound, result);
	}
    
    /*
    Here's the bonus O(log n) solution from a leetcode user.
    */
   public TreeNode successor(TreeNode root, TreeNode p) {
    if (root == null)
        return null;

    if (root.val <= p.val) {
        return successor(root.right, p);
    } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
    }
}

}

class Node {
	int val;
	Node left;
	Node right;

	public Node(int val) {
		this.val = val;
	}
}

Time Complexity

The time complexity is O(n) since we do a complete inorder traversal.