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 Using Parent link

Algo­rithms — Inorder Suc­ces­sor in Binary Search Tree Using Par­ent link

Objec­tive: Given a Binary Search tree in which every node has a link to its par­ent, 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­out par­ent link
Inorder Suc­ces­sor in Binary Tree

Input: A binary search tree with nodes liked to its par­ents, a node x

Out­put: The 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 whose 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 doesnt have a right child then its inorder suc­ces­sor will the one of its ances­tors, using par­ent link keep trav­el­ing up till you get the node which is the left child of its par­ent. Then this par­ent node will be the inorder successor.

InOrder Successor - Case 2

InOrder Suc­ces­sor — 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...