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.

  • abhi­neet kapil

    Very well Explained.

    But minor cor­rec­tion as @sumeet_wilkhu:disqus pointed out.

  • abhi­neet kapil

    What should be the value of suc­ces­sor for the ele­ment 35 (as per the tree cre­ated in main method) ? Since 35 comes last as per in-order tra­ver­sal, shouldn’t its suc­ces­sor be null ?

    Below is the code output :

    In-order Suc­ces­sor of 35 is : 20 and pre­de­ces­sor is : 30