I need an algorithm for returning the successor node of some arbitrary node of the given binary search tree.
+1
A:
There are two general approaches:
- If your binary tree nodes have pointers to their parent node, then you can traverse directly from the node to the successor node. You will have to determine how to use the parent pointers to do the traversal.
- If your binary tree nodes do not have parent pointers, then you will have to do an inorder traversal of the tree starting at the root (presumably you have a root node pointer) and return the next node after the given node.
Greg Hewgill
2009-12-13 19:22:43
In the second case, you can still apply the first method by maintaining a zipper as you descend.
Pascal Cuoq
2009-12-13 19:28:24
There's also a third approach, namely a threaded tree where otherwise null child links are replaced by links pointing to the inorder predecessor or successor. Threaded trees are rarer than your mentioned approaches, probably because they are a bit more complicated to maintain, but they make this problem (and other traversal problems) very easy. GNU libavl has implementations, including for balanced trees.
jk
2009-12-13 19:30:14
If you knew you had such a threaded tree, you wouldn't be asking the original question. :)
Greg Hewgill
2009-12-13 19:46:25
+4
A:
To give you an answer with the same level of detail as your question: Go up until going right is possible, and then left until you reach a leaf.
FRotthowe
2009-12-13 19:23:00
A:
You need to maintain a zipper as you descend the tree. A zipper is simply a list of the nodes you have traversed, and for each an indication of whether you next went left or right. It allows you to travel back up in the tree even if there aren't any pointers from children to parents.
The algorithm for successor is to go back (up in the zipper) as long as you were coming from the left, then go right once, and then descend to the leftmost child.
It's easier with a figure...
Pascal Cuoq
2009-12-13 19:26:28
If you do have details to give, in order of preference:1/ give them in full the first time as you ask the question2/ give them in full in the question by editing it when you realize you weren't precise enough. It's worth expanding three-letter acronyms if you don't want people to lose consideration.
Pascal Cuoq
2009-12-13 19:46:36