# Inorder Successor in a Binary Search Tree

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find Inorder Successor in a Binary Search Tree.

## Problem

Given a Binary Search Tree and a target node value. Find the Inorder successor of the given node value in the Binary Search tree given. Inorder successor of any node ‘x’ is basically the node which gets traversed immediately after ‘x’ in the Inorder traversal of a tree.
Also assume that the node can not be the rightmost node of the given BST as no Inorder successor can exist for such node as this would be the last node to get traversed in the Inorder traversal. Inorder successor of 6 is 7 in this Binary Search Tree.

## Solution

### APPROACH – I :

A basic approach for finding inorder successor of any node in BST can be inspired by the fact that Inorder traversal of any Binary Search tree is sorted which means that Inorder successor of any node ‘x’ is the node having value greater than ‘x’ while being the smallest among all of these nodes having value greater than ‘x’

Let’s call this node as ‘next greater node’ which is actually the Inorder successor.
Now the problem boils down to finding this next greater node having value just greater than given target node.

So, for this, a simple preorder traversal would be enough, where at every node, we compare the node value with the target node and update our final answer if this current node has value greater than target node and lesser than final answer till now.

Time Complexity Discussion :
As we clearly need atleast a complete preorder or any traversal of the given Binary Search tree to explore all the nodes, hence, the worst time complexity of this approach for finding Inorder successor is O(n).

### Approach – II:

We know that `Inorder successor` of any element cannot lie in its left subtree as the Inorder successor of any node will definitely be `greater` than the target node and it is a property of binary search tree that no smaller value node can lie in the left subtree of any node.

Therefore, If a node has a `right child`, then its `inorder successor` should definitely be in the `right subtree` of that node.
Now, there can be two possibilities :

### (i) If the target node has a right child :

As we know, `inorder successor` of any node is the next greater node in a Binary Search tree and next greater node of any node is the leftmost node in the right subtree of that node. In simpler terms, next greater node of any node ‘x’ must be the smallest node among all the nodes having value greater than ‘x’ and we know, right subtree in a Binary Search tree contains all the greater nodes. Now, smallest node among all these greater nodes will be leftmost node. Hence, If the target node has a right child then, its Inorder successor will be leftmost node in its right subtree.

### (ii) If the target node does not have a right child :

Now, as there is `no Right subtree` belonging to the target node, therefore, now we need to find the next greater node in a traversal starting from root, but since we have a Binary search tree to work with hence we can find the next greater node efficiently.
How?
We always start the traversal from root node and compare the value of current node with the target node whose inorder successor has to be found and

• if it is greater than target node value, then update the final answer and move to the left subtree, WHY? because there is no benefit in going to right subtree as we will only find nodes with values greater than this current node, and as this node itself is greater than target node, this means it can be a potential `next greater node` but nodes in its right subtree can certainly not.
• if the current node is smaller than the target node, then move to the right subtree as we are looking for nodes having value greater than value of target node.

## Time Complexity Discussion

Functions in both the cases (node with and without right child) traverse the tree in a linear path, that is, at every level we are either going to left subtree or the right subtree which makes the worst time complexity of this approach to `O(height)` and height of a tree is `O(log n)`, where `n` is the number of nodes.

When you run above program, you will get below output:

6

That’s all about Inorder Successor in a Binary Search Tree.

import_contacts

### You may also like: ## Related Posts

• 10 October

### Convert sorted Linked List to balanced BST

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post , we will see how to convert sorted LinkedList to balanced binary search tree. There are two ways to do it. Solution 1: It is very much similar to convert sorted array to BST. […]

• 10 October

### Convert sorted array to balanced binary search tree

Table of ContentsAlgorithm:Java code to convert sorted array to balanced binary search tree: If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post ,  we will see how to convert sorted array to balanced binary search tree. Algorithm: You might know that inorder traversal of […]

• 16 September

### Check if a binary tree is binary search tree or not in java

Table of ContentsFirst method:Second Method:Complete java program to check if Binary tree is binary search tree or not. If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to check if given binary tree is binary search tree or not. […]

• 16 April

### Delete a node from binary search tree in java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to delete a node from binary search tree. There are two parts to it. Search the node After searching that node, delete the node. There are three cases which we […]

• 15 April

### Binary search tree in java

Table of ContentsSearch()Insert() If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. Binary search tree is a special type of binary tree which have following properties. Nodes which are smaller than root will be in left subtree. Nodes which are greater than root will be right […]

• 15 April

### Find minimum and maximum elements in binary search tree in java

Table of ContentsFinding minimum element:Finding maximum element: If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to find minimum and maximum elements in binary search tree. Finding minimum element: Minimum element is nothing but leftmost node in binary search […]

## Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.