**Algorithms – Inorder Successor in Binary Tree **

**Objective:** Given a Binary tree (Not 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 Search Tree without parent link

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

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

**Example: **

**Approach:**

**NOTE: **since it’s not a binary search tree, we cannot use binary search technique to reach to the node. we need to travel all the nodes in order to find the node for which we need to find the inorder successor.

How to search for a path of any node in binary 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. *

- Start from the root and compare it with x, if matched then we have found the node.
- else go left and right.
- recursively do step 2 and 3 till you find the node x.
- Now when you have found the node, stop the recursion.
- Now recursion will backtrack to the root, every recursive call will return the node itself (say it will be stored in
) so when it backtracked to its parent which will be root now, check whether parent.left = n, if not , keep going up.*n*

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

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class InOrderSuccessorBinaryTree { | |

public static TreeNode n = null; | |

public static Boolean nodeFound = false; | |

public TreeNode inOrderSuccBiTree(TreeNode root, TreeNode x){ | |

nodeFound = false; | |

if(x.right!=null){ | |

TreeNode temp = leftMostTreeNode(x.right); | |

System.out.println("The In Order Successor for '" + x.data + "' is "+ temp.data ); | |

return null; | |

} | |

return findRecur(root, x); | |

} | |

public void display(TreeNode root){ | |

if(root!=null){ | |

display(root.left); | |

System.out.print(" " + root.data); | |

display(root.right); | |

} | |

} | |

public TreeNode findRecur(TreeNode root, TreeNode x){ | |

if(root==null) return null; | |

if(root==x||(n = findRecur(root.left,x))!=null||(n=findRecur(root.right,x))!=null){ | |

if(n!=null){ | |

if(root.left==n){ | |

nodeFound = true; | |

System.out.println("The In Order Successor for '" + x.data + "' is "+ root.data ); | |

return null; | |

} | |

} | |

return root; | |

} | |

return null; | |

} | |

public TreeNode leftMostTreeNode(TreeNode x){ | |

while(x.left!=null){ | |

x = x.left; | |

} | |

nodeFound = true; | |

return x; | |

} | |

public static void main(String args[]){ | |

TreeNode root = new TreeNode('a'); | |

root.left = new TreeNode('b'); | |

root.right = new TreeNode('c'); | |

root.left.left = new TreeNode('d'); | |

root.left.right = new TreeNode('e'); | |

TreeNode x = new TreeNode('x'); | |

root.left.right.left = new TreeNode('i'); | |

root.left.right.left.right = new TreeNode('j'); | |

root.left.right.left.right.right = x; | |

root.right.left = new TreeNode('f'); | |

TreeNode y = new TreeNode('g'); | |

root.right.right = y; | |

InOrderSuccessorBinaryTree i = new InOrderSuccessorBinaryTree(); | |

System.out.print(" Tree : "); | |

i.display(root); | |

System.out.println(); | |

nodeFound = false; | |

i.inOrderSuccBiTree(root, x); | |

if(!nodeFound){ | |

System.out.println("InOrder Successor of " + x.data + " is NULL"); | |

} | |

nodeFound = false; | |

i.inOrderSuccBiTree(root, root); | |

if(!nodeFound){ | |

System.out.println("InOrder Successor of " + root.data + " is NULL"); | |

} | |

nodeFound = false; | |

i.inOrderSuccBiTree(root, y); | |

if(!nodeFound){ | |

System.out.println("InOrder Successor of " + y.data + " is NULL"); | |

} | |

} | |

} | |

class TreeNode{ | |

char data; | |

TreeNode left; | |

TreeNode right; | |

public TreeNode(char data){ | |

this.data = data; | |

this.left = null; | |

this.right = null; | |

} | |

} |

**Output**:

Tree : d b i j x e a f c g The In Order Successor for 'x' is e The In Order Successor for 'a' is f InOrder Successor of g is NULL