title: Converting a Binary Tree to Double Threaded Binary Tree?
body: <p>I could not find anything on search to satisfy my question, if it exists, I'm sorry!</p>
  
  <p>I am working on a college assignment about threaded binary trees. I.e. various kinds of traversals - inorder, postorder and preorder on double TBT.</p>
  
  <p>This is the TBTNode struct:</p>
  
  <pre><code>struct TBTNode {
    TBTNode *left, *right, *parent;       
    char data;
    bool left_normal, right_normal;
    TBTNode(char d) {
      data = d;
      left = NULL;
      right = NULL;
      parent = NULL;
      left_normal = true;
      right_normal = true;
    }
  };
  </code></pre>
  
  <p>As you can see, there is not much distinction between a Binary Tree node and a TBT node, except that the node's properties, viz. {left,right}_normal are set to true when required.</p>
  
  <p>To create the tree, I have this:</p>
  
  <pre><code>class TBT {
    TBTNode *root;
  public:
    TBT() {
      root = new TBTNode(0);
      root-&gt;right = root;
      root-&gt;right_normal = true;          
      cout &lt;&lt; "Root:" ;           
      root-&gt;left = create();
      if(root-&gt;left)
        root-&gt;left_normal = true;
    }
    TBTNode* create();  
  };
  
  TBTNode* TBT::create() {
    char data;
    TBTNode *node = NULL;
    cout &lt;&lt; endl &lt;&lt; "Enter data (0 to quit): ";
    cin &gt;&gt; data;
    if(data == '0')
      return NULL;
    node = new TBTNode(data);
    cout &lt;&lt; endl &lt;&lt; "Enter left child of " &lt;&lt; data;
    node-&gt;left = create();
    if(node-&gt;left)
      node-&gt;left-&gt;parent = node;
    else {
      node-&gt;left = root;
      node-&gt;right = node-&gt;parent;
      node-&gt;left_normal = node-&gt;right_normal = false;
    }
    cout &lt;&lt; endl &lt;&lt; "Enter right child of " &lt;&lt; data;
    node-&gt;right = create();
    if(node-&gt;right)
      node-&gt;right-&gt;parent = node;
    else {
      node-&gt;left = node;
      node-&gt;right = node-&gt;parent-&gt;parent;
      node-&gt;left_normal = node-&gt;right_normal = false;
    }
    return node;
  }
  </code></pre>
  
  <p>After the tree gets recursively created using the above code, I want to convert it into a double threaded binary tree. I know the concept that left child is linked to the child's inorder predecessor and right to inorder successor, but I am unable to create an algorithm. Can someone help me?</p>