title: Right Threading a Binary Tree
body: <p>I'm having a hell of a time trying to figure this one out. Everywhere I look, I seem to be only running into explanations on how to actually traverse through the list non-recursively (the part I actually understand). Can anyone out there hammer in how exactly I can go through the list initially and find the actual predecessor/successor nodes so I can flag them in the node class? I need to be able to create a simple Binary Search Tree and go through the list and reroute the null links to the predecessor/successor. I've had some luck with a solution somewhat like the following:</p>
  
  <pre><code>thread(node n, node p) {
       if (n.left !=null)
          thread (n.left, n);
       if (n.right !=null) {
          thread (n.right, p);
       }
       n.right = p;
  }
  </code></pre>