“Successor and predecessor is something that we see only in a BST. We have seen in a binary tree there is ancestor node, parent node, child node, sibling node. But in a BST, successor node might be necessary to take the nth smallest item in a tree”
Say, you have a BST,
3 17 20
You need to find the 5th smallest element in this or you need to find the next element to 4 which is ”6”. Assume that all the elements are distinct. How would you find that?
- Do a in-order traversal
- Store the whole tree in an array while traversal
- Search for the “4” in the whole array
- The index found +1 will give the successor element
The above approach works well but has the following problems:
- We use O(n) extra space
- If the elements are not identical, we need some more logic to jump across same elements
The above problems are get solved with the concept of successor and predecessor. Successor in a BST for any element is defined by two concepts:
- If the element has a right node, then the min element in the right sub tree (which is the left most element) will be successor.
- If the element doesn’t have a right node, then check whether it has a parent node and also verify whether this element is the right node for its parent.
- Successor node for: 15 is 17 (left-most)
- Successor node for: 4 is 6 (parent of “4” is “3” and move up by parent until “4” is not the right node for the parent. which yields as “6”)
The above properties of a successor in a BST can be used to design a algorithm to find the successor for the given element.
The second property is nothing but finding the least ancestor of the given node which we will use in future.