This post is completed by 2 users

  • 0
 Add to List
Medium

44. Inorder Successor in Binary Tree

Algorithms - Inorder Successor in Binary Tree

Objective: Given a Binary tree (Not 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

Example:

InOrder Successor in binary tree example

Approach:

NOTE: since it's not a binary search tree, we cannot use a binary search technique to reach the node. we need to travel all the nodes 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 found is x.

Case 1: If the x has a right child then its inorder successor will be the leftmost element in the right subtree of x.

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

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

 
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

Also Read :
Inorder Successor in Binary Search Tree with parent link
Inorder Successor in Binary Search Tree without parent link

Related Problems: