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 Search Tree without Using Parent link

Objec­tive: Given a 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 Tree

Input: A binary search tree, a node x

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

Exam­ple:

InOrder Successor example

InOrder Suc­ces­sor example

Approach:

Time Com­plex­ity : O(h) , h — height of the 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 - Case 1

InOrder Suc­ces­sor — Case 1

Case 2: If the x doesn’t have a right child then its inorder suc­ces­sor will the one of its ances­tors, use the binary search tech­nique to find the node x, start from the root, if root is big­ger than the x then go left, if root is less than x, go right. while trav­el­ing when­ever you go left , store the node and call it successor.

InOrder Successor - use binray search techique - Case 2

InOrder Suc­ces­sor — use bin­ray search techique — 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 : 3 5 7 10 17 15
InOrder Successor of 7 is 10
InOrder Successor of 10 is 17

You may also like...