Threaded Binary Search Trees Advantage

Question

An explanation about Threaded Binary Search Trees (skip it if you know them):

We know that in a binary search tree with n nodes, there are n+1 left and right pointers that contain null. In order to use that memory that contain null, we change the binary tree as follows -

for every node z in the tree:

if left[z] = NULL, we put in left[z] the value of tree-predecessor(z) (i.e, a pointer to the node which contains the predecessor key),

if right[z] = NULL, we put in right[z] the value of tree-successor(z) (again, this is a pointer to the node which contains the successor key).

A tree like that is called a threaded binary search tree, and the new links are called threads.

And my question is: What is the main advatage of Threaded Binary Search Trees (in comparison to "Regular" binary search trees). A quick search in the web has told me that it helps to implement in-order traversal iteratively, and not recursively.

Is that the only difference? Is there another way we can use the threads?

Is that so meaningful advantage? and if so, why? Recursive traversal costs O(n) time too, so..

Thank you very much.

Recursive traversal is O(n) time complexity, with an O(logN) space requirement (average case) and O(N) space requirement in the worst case. On the other hand, a threaded binary tree has an O(1) space requirement in the worst case, if the traversal is done iteratively. — amnn

Jim Mischel Jim Mischel · Accepted Answer · 2014-01-06T14:50:36

Non-recursive in-order scan is a huge advantage. Imagine that somebody asks you to find the value "5" and the four values that follow it. That's difficult using recursion. But if you have a threaded tree then it's easy: do the recursive in-order search to find the value "5", and then follow the threaded links to get the next four values.

Similarly, what if you want the four values that precede a particular value? That's difficult with a recursive traversal, but trivial if you find the item and then walk the threaded links backwards.

Threaded Binary Search Trees Advantage

2 Answers