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 Predecessor and Successor in Binary Search Tree

Objec­tive: - Given a Binary Search Tree, Find pre­de­ces­sor and Suc­ces­sor of a given node.

What is Pre­de­ces­sor and Successor :

When you do the inorder tra­ver­sal of a binary tree, the neigh­bors of given node are called Pre­de­ces­sor(the node lies behind of given node) and Suc­ces­sor (the node lies ahead of given node).

Exam­ple:

Inorder-Predecessor-and-Successor-in-Binary-Search-Tree

Inorder-Predecessor-and-Successor-in-Binary-Search-Tree

Approach:

Say you have to find the inorder pre­de­ces­sor and suc­ces­sor node 15.

  • First com­pare the 15 with root (25 here).
  • 25>15 => suc­ces­sor = 25, make recur­sive call to root.left.(Why do we do it , is explained at step 3).
  • New root which is = 15, now stop mak­ing recur­sive calls.
  • Now suc­ces­sor will be the left most node in right sub­tree of which has the root 18 here. So the left most ele­ment and suc­ces­sor will be 19. (What if 15 doesn’t have a right sub­tree, then suc­ces­sor of 15 will be the par­ent of it, and that is why we set par­ent as suc­ces­sor in step1).
  • Now pre­de­ces­sor will be the right most node in left sub­tree which has the root 10 here. but 10 doesn’t have right child.
  • For the same rea­son when node<root then make pre­de­ces­sor = root and make a recur­sive call to the root.right.

Com­plete Code:


Out­put:

Inorder Successor of 10 is : 13 and predecessor is : 7
Inorder Successor of 30 is : 35 and predecessor is : 25

You may also like...

  • Sumeet Wilkhu

    I think your “BST” exam­ple and approach demon­stra­tion is par­tially incor­rect. The node 19 can­not be left child of 18 as 19 is obvi­ously greater than 18. This vio­lates the basic prin­ci­ple of binary search tree where left child should always be less than or equal to par­ent and right child should be greater than par­ent. I would sug­gest you to replace 19 with 17 and the suc­ces­sor for 15 then becomes 17, oth­er­wise, if right sub-tree doesn’t exist, the suc­ces­sor for 15 becomes 25. Please cor­rect that. Thank you.