Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Inorder Successor in Binary Tree

Algo­rithms — Inorder Suc­ces­sor in Binary Tree

Objec­tive: Given a Binary tree (Not binary Search Tree ), find the inorder suc­ces­sor of a node.

What is Inorder Suc­ces­sor: Inorder suc­ces­sor of a node is the next node in the inorder tra­ver­sal of the tree. For the last node in a tree, inorder suc­ces­sor will be NULL

Sim­i­lar Prob­lems :
Inorder Suc­ces­sor in Binary Search Tree with par­ent link
Inorder Suc­ces­sor in Binary Search Tree with­out par­ent link

Input: A binary tree, a node x

Out­put: Inorder suc­ces­sor of node x.

Exam­ple:

InOrder Successor in binary tree example

InOrder Suc­ces­sor in binary tree example

Approach:

NOTE: since it’s not a binary search tree, we can­not use binary search tech­nique 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 suc­ces­sor needs to be find is x.

Case 1 : If the x has a right child then its inorder suc­ces­sor will the left most ele­ment in the right sub tree of x.

InOrder Successor in binary tree case 1

InOrder Suc­ces­sor in binary tree case 1

  1. Start from the root and com­pare it with x, if matched then we have found the node.
  2. else go left and right.
  3. recur­sively do step 2 and 3 till you find the node x.
  4. Now when you have found the node, stop the recursion.
  5. Now recur­sion will back­track to the root, every recur­sive call will return the node itself (say it will be stored in n) so when it back­tracked to its par­ent which will be root now, check whether parent.left = n, if not , keep going up.
InOrder Successor in binary tree case 2

InOrder Suc­ces­sor in binary tree case 2

Case 3: if x is the right most node in the tree then its inorder suc­ces­sor will be NULL.

Com­plete Code:


Out­put:

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

You may also like...