Benefits of Threaded Binary Search Trees

Question

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 pointers left and right that contain null. To use this memory containing zero, we change the binary tree as follows:

for each node z in the tree:

if left [z] = NULL, we put left [z] the value of tree-predecessor (z) (that is, a pointer to a node that contains the predecessor key),

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

A tree like this is called a carved tree , and new links are called threads .

And my question is: What is the main advantage of threaded binary search trees (compared to “regular” binary search trees). A quick search on the Internet told me that it helps to crawl in an iterative manner rather than a recursive manner.

Is that the only difference? Is there any other way to use threads?

Is this such a significant advantage? and if so, why? The recursive bypass time is O (n) too, so ..

Thank you very much.

Answer 1

Non-recursive scanning is fine - a huge advantage. Imagine that someone asks you to find the value "5" and the four values ​​that follow it. This is complicated with recursion. But if you have a threaded tree, then this is easy: do a recursive search in order to find the value "5", and then follow the streaming links to get the next four values.

Similarly, what if you need four values ​​preceding a particular value? This is tricky with recursive traversal, but trivial if you find an element and then skip the streaming links back.

Answer 2

The main advantage of threaded binary search trees compared to the usual one is that it is more efficient in the first case compared to the other.

Recursive movement means you don't need to implement it with a stack or queue. Each node will have a pointer that will more effectively use the inorder successor and predecessor, while at the same time implementing movement in the regular BST stack, which is an exhaustive amount of memory (since here the programming language should take into account the implementation of the stack).