Hello every one!
I just want to share my code for finding “In-order Successor” of any node in ANY binary tree WITHOUT parent pointer. The tree need NOT be a BST. This piece of code returns the address of the inorder successor of any node identified by the key value passed with O(logn) time complexity. Complexity increases to O(n) for the worst case (when the tree is skewed).
typedef struct Node //Basic structure of my tree node{ int data; Node *left,*right;} Node;Node *findRightSuccessor(Node *root){ while (root->left) root=root->left; return root;}Node *inorderSuccessor(Node *root, int key, Node *parent){ if (root==NULL) return 0; if (root->data == key) { if (root->right) return findRightSuccessor(root->right); else return parent; } Node *left=inorderSuccessor(root->left,key,root); if (left) return left; return inorderSuccessor(root->right,key,parent);}Node *inorderSuccessor(Node *root, int key){ return inorderSuccessor(root,key,NULL);} |
The function visible to end user is the last one. Which in turns calls an overloaded version of itself.
rajneesh2k10 
#1 by Randomguy on November 13, 2013 - 21:34
this is great
#2 by rajneesh2k10 on November 13, 2013 - 21:53
Thanks 🙂
#3 by Herman on March 10, 2014 - 05:09
Does it work for a tree like this?
0
/
1
\
2
Find successor of 2 would return 1 in your algo, but it should return 0.
#4 by rajneesh2k10 on March 23, 2014 - 07:17
Hey Herman,
Sorry for the delay in my response. I couldn’t give immediate attention because of being occupied with something else.
It does work for the case you are talking. Did you try to run it and see? Can you share your code where you did this experiment?
My small experiment shows correct result for the case you mentioned. Here is the experimental code: http://ideone.com/OiTJca
Have a nice day!
#5 by kelkarn on March 23, 2014 - 05:51
Dude, this is really great! Because the code is not self explanatory, it would be nice to have an example that works with just three nodes (root, left and right) and demonstrate how this algorithm works. Maybe that is something I can blog about? 😉
In any case, an awesome blog! 🙂
#6 by rajneesh2k10 on March 23, 2014 - 07:23
Hi Kelkarn,
Really nice to hear that you liked my approach and blog. 🙂
As you suggested I’ll add explanation of this algorithm with an example to make it more clear.
Thanks for admiring. It keeps me alive. 🙂
#7 by Ayush Jain on July 9, 2014 - 01:49
void inorderSuccessorUtil(Node *root,int key,Node** next,Node **successor)
{
if (root==NULL)
return;
inorderSuccessorUtil(root->right,key,next,successor);
if(root->data == key)
{
*successor=*next;
}
else
*next=root;
inorderSuccessorUtil(root->left,key,next,successor);
}
int inorderSuccessor(Node *root, int key)
{
int flag=0;
Node* successor,*next=NULL;
inorderSuccessorUtil(root,key,&next,&successor);
if(!successor)
return -1;
else
return successor->data;
}
#8 by prashantsahu on January 6, 2015 - 13:57
Hey Rajneesh,
Can you explain me how it works for a case like :
(1)
(2) (3)
(4) (5) (6) (7)
If i say key = 4, this works fine, but if i say key = 5, it still returns (2).
But Ideally it should return (1)
#9 by rajneesh2k10 on January 20, 2015 - 09:46
Hi Prashant,
Have you run this program? ‘m sure you have not. You’ll get 1 and not 2.
If you have just walk through- mind it when you are traversing right child you are passing the parent and not the root itself.
Hope that helps.
Have a nice day!
#10 by Marija Popova on January 17, 2015 - 01:44
hey i want this algorithm in java programming language.If anyone can do that please..
#11 by rajneesh2k10 on January 20, 2015 - 09:49
Hi Marjia,
You should try it yourself. I can help you with any roadblock if you hit.
All the best!
#12 by pcshortcutblog on March 23, 2017 - 16:14
umm… I don’t find c++ and Java too different from each other so you shouldn’t have any problem in understanding these fuctions and once you have understood them you can easily write them in Java. Good Luck!!
#13 by Nitika on October 7, 2015 - 17:06
Node inOrderSuccessor(Node root, int key, Node parent)
{
if(root.getData() == key)
{
if(root.getRight()!=null)
return leftMostNode(root.getRight());
else
return parent;
}
Node left = inOrderSuccessor(root.getLeft(), key, root);
if(left != null)
{
return left;
}
return inOrderSuccessor(root.getRight(), key, parent);
}
Node leftMostNode(Node root)
{
while(root.getLeft()!=null)
{
root.setLeft(root);
}
return root;
}
Node inOrderSuccessor(Node root, int key)
{
return inOrderSuccessor(root, key, null);
}
public static void main(String[] args)
{
inOrderSuccessor(root, 20);
}
This gives me null pointer exception when I run this code.
my tree:
45
( 25 75)
(15 35)
(10,20) (30,35)
#14 by vikas on January 4, 2016 - 08:39
Works like a charm. Could you also post the predecessor code, please? I tried like so in Python, but didn’t work:
def find_inorder_predecessor(root, target, parent=None):
if not root:
return None
if root.data == target:
if root.left:
return max_value(root.left) #defined elsewhere; simple function
return parent
if root.data > target:
return find_inorder_predecessor(root.left, target, root)
return find_inorder_predecessor(root.right, target, parent)
#15 by abbikazmi on April 9, 2017 - 19:44
helpful post…but in order to understand how to find predecessor & successor in binary search tree following link is quite helpful also: