title: what should be the structure of binary search tree node
body: <p>i am trying to make c++ program for binary search tree which will contain following functionality (actually this is a part of my college assignment):</p>
  
  <p>A) CREATE Binary search tree.</p>
  
  <p>B) Inorder, preorder, postorder traversals. ( non-recursive )</p>
  
  <p>C) Search the Val in tree.</p>
  
  <p>D) Breadth first traversal.     </p>
  
  <p>E) Depth first traversal</p>
  
  <p>F) Count leaf nodes, non-leaf nodes.</p>
  
  <p>G) Count no. of levels  </p>
  
  <p>my doubt is:-</p>
  
  <p><strong>1.</strong> usually a tree node have following structure:</p>
  
  <pre><code>class node{
  
   private:
     node *lChild;
     int info;
     node *rChild;
  }
  </code></pre>
  
  <p>so in case i want to  perform depth-first or breadth-first traversal can i change the node structure and add one more pointer pointing to the parent so that i can easily move backward in the hierarchy</p>
  
  <pre><code>class node{
  
   private:
     node *parent //pointer to parent node
     node *lChild;
     int info;
     node *rChild;
  }
  </code></pre>
  
  <p>is this considered as normal practice or bad form of programming a binary tree ? and if it is not considered as good way of programming a tree is there any other way or do i have to use the method given in books of using stack (for Depth First) and queue(for breadth first) to store nodes (visited or non-visited accordingly)</p>
  
  <p><strong>2.</strong> This is first time i am learning data structures so it will be a great help if someone can explain in simple words that what is the difference between recursive and non-recursive traversal with binary tree in consideration</p>