/*

A simple implentation of a Binary Search Tree (BST)  on an Arduino Uno R3.

A node has two pointers -- one to the left and one to the right -- to other
nodes in the tree. The first node inserted is the root and has no parents,
nodes can only have two children maximum and any node without children is
a leaf.

When a node is inserted into the tree it checks to see if its greater
than the root node and sends it down the tree to right where it continues
to make comparisons. If the node is lesser than the root node's value it
does the same but to the left.

The inserted node keeps transversing the tree until it finds a node with
less than two children and inserts itself. This results in a tree with efficient
methods to both insert new nodes and search the tree for values.

An in-order transverse of the node starts at the leftmost node which is
the least valued node and continues, in order of values, to the rightmost
one which is the greatest valued node.








*/




// Define the structure of a tree node
struct Node {
  int data;           // Data of the node (integer in this case)
  Node* left;         // Pointer to the left child node
  Node* right;        // Pointer to the right child node
};

// Function to create a new node
Node* createNode(int value) {
  Node* newNode = new Node();
  newNode->data = value;
  newNode->left = nullptr;
  newNode->right = nullptr;
  return newNode;
}

// Function to insert data into the tree
Node* insert(Node* root, int value) {
  if (root == nullptr) {
    // If the tree is empty, create a new node
    return createNode(value);
  }

  if (value < root->data) {
    // Insert in the left subtree
    root->left = insert(root->left, value);
  } else if (value > root->data) {
    // Insert in the right subtree
    root->right = insert(root->right, value);
  }

  // Return the unchanged root pointer
  return root;
}

// Function to perform in-order traversal of the tree
void inOrderTraversal(Node* root) {
  if (root == nullptr) {
    return;
  }

  // Traverse the left subtree
  inOrderTraversal(root->left);

  // Visit the root node
  Serial.print(root->data);
  Serial.print(" ");

  // Traverse the right subtree
  inOrderTraversal(root->right);
}

// Function to search for a value in the tree
bool search(Node* root, int value) {
  if (root == nullptr) {
    return false; // The tree is empty, or we've reached a leaf node
  }

  if (root->data == value) {
    return true;  // Found the value
  }

  if (value < root->data) {
    return search(root->left, value);  // Search in the left subtree
  } else {
    return search(root->right, value); // Search in the right subtree
  }
}

// Global variable to store the root of the tree
Node* root = nullptr;

void setup() {
  // Initialize the serial monitor
  Serial.begin(9600);
  
  // Insert values into the tree
  root = insert(root, 50);
  insert(root, 30);
  insert(root, 20);
  insert(root, 40);
  insert(root, 70);
  insert(root, 60);
  insert(root, 80);
  insert(root, 45);
  insert(root, 32);
  insert(root, 105);

  // Display the tree in in-order traversal
  Serial.println("In-order traversal of the tree:");
  inOrderTraversal(root);
  Serial.println();

  // Search for a value in the tree
  int searchValue = 45;
  if (search(root, searchValue)) {
    Serial.print("Value ");
    Serial.print(searchValue);
    Serial.println(" found in the tree.");
  } else {
    Serial.print("Value ");
    Serial.print(searchValue);
    Serial.println(" not found in the tree.");
  }
}

void loop() {
  // Do nothing in the loop
}