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

*What is Inorder Successor: **Inorder successor of a node is the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL*

**Similar Problems : **

Inorder Successor in Binary Search Tree with parent link

Inorder Successor in Binary Tree

**Input:** A binary search tree, a node x

**Output: Inorder successor of node x.**

**Example: **

InOrder Successor example

**Approach:**

**Time Complexity : O(h) , h – height of the tree**

**There will be 3 cases to solve this problem**

Say the node for which inorder successor needs to be find is **x.**

*Case 1 : If the x has a right child then its inorder successor will the left most element in the right sub tree of x. *

InOrder Successor – Case 1

*Case 2: **If the x doesn’t have a right child then its inorder successor will the one of its ancestors, ***use the binary search technique to find the node x, start from the root, if root is bigger than the x then go left, if root is less than x, go right. while traveling whenever you go left , store the node and call it successor.**

InOrder Successor – use binray search techique – Case 2

*Case 3: if x is the right most node in the tree then its inorder successor will be NULL.*

**Complete Code:**

**Output**:

Tree : 3 5 7 10 17 15
InOrder Successor of 7 is 10
InOrder Successor of 10 is 17

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*