Problem

Given a Binary Search tree, find the inorder successor of a node.

Definition

See the definition here.

Examples

Example 1:

   10
  /  \
 5    30
     /  \
   22    35

Input: root = [10,5,30,null,null,22,35], node = 22
Output: 30

Similar Problem

Inorder Successor in Binary Search Tree Using Parent link Inorder Successor in Binary Tree

Solution

Method 1 - Iterative

Lets call our node X, where we are trying to find the inorder success of X.

Now, we have 2 cases.

Case 1 - Node X has right child

If the node has a right child, The in-order successor is the leftmost node in the node’s right subtree.

For example, for below given tree, the inorder successor of node 30 is 33.

graph TD;
10 --- 5 & 30
30 --- 22 & 35
35 --- 33 & 38

style 30 fill:#FF9933
style 33 fill:green

Case 2 - Node X has no right child

Case 2.1 - We find our answer

If the node does not have a right child, start from the root and use a variable to keep track of the potential successor as you traverse down the tree.

For eg. in the tree given below, we try to find inorder successor of 8. We see 10 is potential inorder successor. Then, we go left. Now, we see 5, which is less than 8, so we go right. We see 7, which is less than 8, so we again go right. Now, we see 8, then 10 is our answer.

graph TD;
10 ---|10>8| 5
10 --- 30
5 --- 1 
5 ---|5<8| 7
7 --- 6
7 ---|7<8| 8
30 --- 22 & 35
35 --- 33 & 38

style 8 fill:#FF9933
style 10 fill:green
linkStyle 0 stroke:red
linkStyle 3 stroke:red
linkStyle 5 stroke:red
Case 2.2 - We dont find answer
Case 2.2 - We dont find answer

If we can’t find such node, than node X is actually the right most child, and we don’t have any inorder successor for it, and hence we return null.

For eg. for node 38, we don’t have any answer.

graph TD;
10 --- 5 & 30
30 --- 22 & 35
35 --- 33 & 38

style 38 fill:#FF9933

Code

Java
public class Solution {

	public TreeNode inorderSuccessor(TreeNode root, TreeNode node) {
		TreeNode successor = null;

		if (node.right != null) {
			return findMin(node.right);
		}

		while (root != null) {
			if (node.val < root.val) {
				successor = root;
				root = root.left;
			} else if (node.val > root.val) {
				root = root.right;
			} else {
				break;
			}
		}

		return successor;
	}

	private TreeNode findMin(TreeNode node) {
		while (node.left != null) {
			node = node.left;
		}

		return node;
	}

}

Complexity

  • ⏰ Time complexity: O(h) where h is height of the tree.
  • 🧺 Space complexity: O(1)

Method 2 - Using Stack

We can use the stack to do the same thing. We will run the inorder traversal on the stack. As soon as we find the node, we know the next in-order traversal will be our answer. We can use an isNext flag, to indicate whether the next node visited should be the in-order successor.

Code

Java
public TreeNode inorderSuccessor(TreeNode root, TreeNode node) {
	Stack<TreeNode> stack = new Stack<>();

	if (root == null || node == null) {
		return null;
	}

	stack.push(root);
	boolean isNext = false;

	while (!stack.isEmpty()) {
		TreeNode top = stack.pop();

		if (top.right == null && top.left == null) {
			if (isNext) {
				return top;
			}

			if (node.val == top.val) {
				isNext = true;
			}

			continue;
		}

		if (top.right != null) {
			stack.push(top.right);
			top.right = null;
		}

		stack.push(top);

		if (top.left != null) {
			stack.push(top.left);
			top.left = null;
		}
	}

	return null;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Cons: Also modifies the tree.