title: Threaded Binary Search Trees Advantage
body: <p>An explanation about Threaded Binary Search Trees (skip it if you know them):</p>
  
  <p>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 -</p>
  
  <p>for every node z in the tree:</p>
  
  <p>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),</p>
  
  <p>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).</p>
  
  <p>A tree like that is called a <strong>threaded binary search tree</strong>, and the new links are called <strong>threads</strong>.</p>
  
  <p><strong>And my question is:</strong>
  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.</p>
  
  <p>Is that the only difference? Is there another way we can use the threads?</p>
  
  <p>Is that so meaningful advantage? and if so, why?
  Recursive traversal costs O(n) time too, so..</p>
  
  <p>Thank you very much.</p>