Problem

Given a node in a binary search tree, return the next bigger element, also known as the inorder successor.

You can assume each node has a parent pointer.

Definition

See the definition here. Here is gist though: The in-order successor of a node in a BST is the next node in in-order traversal, which, for a given node, is the node with the smallest value larger than the given node’s value.

Examples

Example 1:

   10
  /  \
 5    30
     /  \
   22    35

Input: node = 22
Output: 30

Similar Problem

Inorder Successor in Binary Search Tree Inorder Successor in Binary Tree

Solution

Method 1 - Follow the definition

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

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

Traverse up using the parent pointers until you find an node which is the left child of its parent. The parent of that node is the in-order successor. So, we have to find an ancestor node, which is left child of its parent, parent of that ancestor is our answer.

For eg. if we want to find the inorder successor or 8, then 5 is the ancestor which is that ancestor, who is left child of its parent, and parent 10 is our answer.

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

style 8 fill:#FF9933
style 10 fill:green
style 5 fill:#00758f
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

TreeNode:

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode parent;
	TreeNode(int x) {
		val = x;
	}
}

Solution:

public class Solution {

	public TreeNode inorderSuccessor(TreeNode node) {
		// Case 1: Node has a right child
		if (node.right != null) {
			return findMin(node.right);
		}

		// Case 2: Node does not have a right child
		TreeNode parent = node.parent;
		TreeNode current = node;

		while (parent != null && parent.right == current) {
			current = parent;
			parent = parent.parent;
		}

		return parent;
	}

	// Helper method to find the leftmost node in a subtree
	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. For an unbalanced BST, the height in the worst case can be O(n).
  • 🧺 Space complexity: O(1)