Preorder Successor value for any node X means value of node Y that comes just after node X while doing Preorder traversal. For given tree in figure, preorder traversal (Root Left Right) would be : 1 2 4 5 3 6. We can search preorder successor for any node by just looking at this traversal output. E.G. preorder successor of node '3' is node '6' because '6' appears after '3' in given traversal.
But in real life we encounter Preorder Successor to be search for any node randomly, and if we go by this method of doing preorder traversal first then giving successor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Preorder Successor randomly for any node without doing traversal explicitly in less time complexity.
Luckily preorder traversal follows some pattern which can help us in giving Preorder Successor for any node without doing traversal at all.
Following is simple algorithm for finding Preorder Successor of binary tree.
Step 1: Current root itself is NULL, then successor is also NULL.
Step 2: Current root contains value same as key for which we are looking successor.
2.1: Current root has right child, then left most node of right child is successor.
2.2: Current root does have right child r, then r is successor.
2.3: Current root is left leaf node and having sibling on right side
2.3: Current root is left leaf node and having sibling on right side
2.4: Otherwise, if current root has an ancestor, v, which is a left-child and v has a right sibling, vrs, then succ(current root) is vrs
2.5: If none of above applies, then succ(current root) doesn't exist.
2.5: If none of above applies, then succ(current root) doesn't exist.
Step 3: Current root is not the target node for which we are looking successor.
3.1: Search target node and its successor in left side of tree recursively, and return if found.
3.2: Search target node and its successor in right side of tree recursively, and return.
Following is implementation of above algorithm in c language.
Please write comments if you find anything wrong or you want to add something more related to this topic.
3 comments:
This Algo does not take care of the below case:
(Remove 5 from the above tree)
For the tree:
// 1
// / \
// 2 3
// / /
// 4 6
It shows succ of 4 as NULL, rather it should be 3
you can find the correction here.
http://ideone.com/4xyYQy
Please fix the comments. Both the comments seems to be saying the same thing
//Case 2.1: Current root has right child, then left most node of right child is successor.
//Case 2.2: Current root does have right child r, then r is successor.
Post a Comment
Write your comment here.