// Soln 9_4.cpp
  // To use rand_s function you must first define _CRT_RAND_S
  define _CRT_RAND_S             // For secure random number generator
  include <iostream>
  include <iomanip>
  include <cstdlib>              // For rand_s function
  
  using std::cout;
  using std::endl;
  using std::setw;
  
  class CBinaryTree
  {
  private:
    class CNode
    {
    public:
      // Node constructor
      CNode(int n) : value(n), m_pLeft(0), m_pRight(0) {}
  
      // List the node values in order
      void listNode()
      {
  
        if(m_pLeft != 0)                 // If there's a left node
          m_pLeft->listNode();           // Output its value
  
        cout << setw(12) << value;       // Output the current node value
        if(++listCount % 5 == 0)
          cout << endl;
  
        if(m_pRight != 0)                // If there's a right node
          m_pRight->listNode();          // Output its value
      }
  
      int value;                         // Value of the node
      CNode* m_pLeft;                    // Pointer to left node
      CNode* m_pRight;                   // Pointer to right node
      static int listCount;              // Count of number of output values
    };
  
  public:
    CBinaryTree() : m_pRoot(0){}         // Constructor
  
    void add(int n);                     // Adds a value to the tree
    void add(int n, CNode* pNode);       // Adds n relative to pNode node
  
    // List the nodes in sequences
    void listNodes()
    {
      CNode::listCount = 0;
      if(m_pRoot == 0)
        cout << "Binary tree is empty." << endl;
      else 
        m_pRoot->listNode();
    }
  
  private:
     CNode* m_pRoot;                     // Pointer to the roor node
  };
  
  int CBinaryTree::CNode::listCount = 0; // Initialize static member
  
  // Add a value to the tree
  void CBinaryTree::add(int n)
  {
    if(m_pRoot == 0)                     // If there's no root node
      m_pRoot = new CNode(n);            // the new node is the root
    else                                 // otherwise
      add(n, m_pRoot);                   // add the node (recursive)
  }
  
  // Add a value relative to a given node
  void CBinaryTree::add(int n, CNode* pNode)
  {
    if(n == pNode->value)                // If value equals current node
    { // Always add equal values as left node
      CNode* pNewNode = new CNode(n);    // Create the new node for the value
      CNode* pTemp = pNode->m_pLeft;     // Save left ptr for current node
      pNode->m_pLeft = pNewNode;         // then make it point to new node
      pNewNode->m_pLeft = pTemp;         // Left ptr for new node point to old left node
    }
    else if(n > pNode->value)            // If new value is greater than right node value
    {                                    // it must go to the right
      if(pNode->m_pRight == 0)           // so if there's no right node
        pNode->m_pRight = new CNode(n);  // make the new node the right node
      else                               // Otherwise
        add(n, pNode->m_pRight);         // add it relative to right node(recursive)
    }
    else                                 // New number is less than current node value
    {
      if(pNode->m_pLeft == 0)            // so if there's no left node
        pNode->m_pLeft = new CNode(n);   // make the new node the left node
      else                               // Otherwise
        add(n, pNode->m_pLeft);          // add it relative to the left node(recursive)
    }
  }
  
  int main()
  {
    CBinaryTree tree;                    // Create a binary tree
    unsigned int number = 0;             // Stores a number to be added to the tree
  
    cout << "Random value inserted in the tree are:" << endl;
  
    // Add 100 random number to the tree
    for(int i = 0 ; i<100 ; i++)
    {
      if(rand_s(&number) != 0)
        cout << "Random number generator failed!" << endl;
      tree.add(number);
      cout << setw(12) << number;
      if((i+1) % 5 == 0)
        cout << endl;
    }
    cout << endl << "Output from the tree is:" << endl;
    tree.listNodes();
  
     return 0;
  }