You are not logged in.
We know that there are n+1 left and right pointers in a binary search tree with n nodes that contain null. To use the memory that contains null, we modify the binary tree as follows -
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.
Hello, my name is Hikam, and I'm a Prolific Java programmer with 4+ years of experience and a solid background in RESTful and JSP development. OddPointer is looking for efficient programming. In recent years, I have built an average of 10+ native Java apps per year. I'm also familiar with C++, C, and HTML, and am actively learning CSS and Python.
Offline
By keeping extra pointers to the in-order successors and predecessors, you can iterate over the binary tree like a list.
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
Offline