Imagine a usual binary search tree with ordered keys, where each node also has a link for next (the leftmost node in right child) and previous (the rightmost node in left child) nodes. How such a data structure is called (if there is a name for it)?
1 Answers
1
votes
What you describe sounds like a special case of threaded binary tree, with the binary tree itself is binary search tree.
One type of threaded binary tree is called "Double threaded binary tree": each node is threaded towards both the in-order predecessor and successor (left and right).
In you case for binary search tree, the rightmost node in left child is actually the in-order predecessor and the leftmost node in right child is actually the in-order successor.
