The maximum stack depth of recursive traversal is proportional to the height of the binary tree. If your binary tree is degenerate, it is possible to overflow the stack.

Without these "thread linkages", implementing an iterative version will also require you to have your own "stack" to store the state required to find the next node. Doing this avoids any stack overflow because your "stack" is actually on the heap and unlimited.

But this iterative in-order traversal code looks terrible.

Using this threaded binary tree allows you iterate like you would with a list.

Thats the only advantage

or 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).

This type of tree is known as a threaded binary search tree, and the new linkages are known as threads.

And my question is, what are the primary benefits of Threaded Binary Search Trees? (in comparison to "Regular" binary search trees). I read this article that said that it is preferable to implement in-order traversal repeatedly rather than recursively.

Is that the only distinction? Is there any method to employ the threads? Is that a significant advantage? If so, please explain why. Recursive traversal also takes O(n) time.