This post is completed by 1 user

  • 0
Add to List
Hard

43. Inorder Successor in Binary Search Tree without Using Parent link

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

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 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 - Case 1

Case 2: If the x doesn't have the right child then its inorder successor will one of its ancestors, use the binary search technique to find the node x, start from the root, if the root is bigger than the x then go left, if the 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 rightmost node in the tree then its inorder successor will be NULL.

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

Also Read :

Inorder Successor in Binary Search Tree with parent link
Inorder Successor in Binary Tree