// Soln9_5.cpp : main project file.
  
  include <stdafx.h>
  
  using namespace System;
  
  ref class BinaryTree
  {
  private:
    ref class Node
    {
    public:
      // Node constructor
      Node(int n) : value(n), left(nullptr), right(nullptr) {}
  
      // List the node values in order
      void listNode()
      {
  
        if(left != nullptr)               // If there's a left node
          left->listNode();               // Output its value
  
        Console::Write(L"{0, 12}", value); // Output the current node value
        if(++listCount % 5 == 0)
          Console::WriteLine();
  
        if(right != nullptr)             // If there's a right node
          right->listNode();             // Output its value
      }
  
      int value;                         // Value of the node
      Node^ left;                        // Reference to left node
      Node^ right;                       // Reference to right node
      static int listCount;              // Count of number of output values
    };
  
  public:
    BinaryTree() : root(nullptr){}       // Constructor
  
    void add(int n);                     // Adds a value to the tree
    void add(int n, Node^ node);         // Adds n relative to pNode node
  
    // List the nodes in sequences
    void listNodes()
    {
      Node::listCount = 0;
      if(root == nullptr)
        Console::WriteLine(L"Binary tree is empty.");
      else 
        root->listNode();
    }
  
  private:
     Node^ root;                         // Reference to the root node
  };
  
  // Add a value to the tree
  void BinaryTree::add(int n)
  {
    if(root == nullptr)                  // If there's no root node
      root = gcnew Node(n);              // the new node is the root
    else                                 // otherwise
      add(n, root);                      // add the node (recursive)
  }
  
  // Add a value relative to a given node
  void BinaryTree::add(int n, Node^ node)
  {
    if(n == node->value)                 // If value equals current node
    { // Always add equal values as left node
      Node^ newNode = gcnew Node(n);     // Create the new node for the value
      Node^ temp = node->left;           // Save left for current node
      node->left = newNode;              // then make it refeence to new node
      newNode->left = temp;              // left for new node refer to old left node
    }
    else if(n > node->value)             // If new value is greater than right node value
    {                                    // it must go to the right
      if(node->right == nullptr)        // so if there's no right node
        node->right = gcnew Node(n);     // make the new node the right node
      else                               // Otherwise
        add(n, node->right);             // add it relative to right node(recursive)
    }
    else                                 // New number is less than current node value
    {
      if(node->left == nullptr)          // so if there's no left node
        node->left = gcnew Node(n);      // make the new node the left node
      else                               // Otherwise
        add(n, node->left);              // add it relative to the left node(recursive)
    }
  }
  
  int main(array<System::String ^> ^args)
  {
    BinaryTree^ tree = gcnew BinaryTree; // Create a binary tree
    unsigned int number = 0;             // Stores a number to be added to the tree
    Random^ generator = gcnew Random;
  
    Console::WriteLine(L"Random value inserted in the tree are:");
  
    // Add 100 random number to the tree
    for(int i = 0 ; i<100 ; i++)
    {
      number = generator->Next(1, 10000);
      tree->add(number);
      Console::Write(L"{0,12}",number);
      if((i+1) % 5 == 0)
        Console::WriteLine();
    }
    Console::WriteLine(L"Output from the tree is:");
    tree->listNodes();
  
     return 0;
  }