using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinaryTreeActual { //Integer Binary Tree
  class Program {
    static void Main(string[] args) {
      Tree tree = new Tree(new IntNode(8, null));
      tree.InsertInt(7);
      tree.InsertInt(9);
      tree.InsertInt(10);
      Console.WriteLine(tree.getDepth(10));
      Console.WriteLine(tree.root.childRight.childRight.value);
      Console.ReadLine();

      foreach (string meme in tree.printFuckingEverything()) {
        Console.WriteLine(meme);
      }

      Console.ReadLine();
    }
  }

  public class Utility {
    public Tree insert(Tree tree, IntNode nodeToAdd, IntNode currentNode = null) {
      if (currentNode == null) {
        currentNode = tree.root;
      }

      if (currentNode.value >= nodeToAdd.value) {
        if (currentNode.childLeft == null) {
          currentNode.childLeft = nodeToAdd;
          return tree;
        }
        else {
          return insert(tree, nodeToAdd, currentNode.childLeft);
        }
      }
      else {  //(currentNode.value < nodeToAdd.value)
        if (currentNode.childRight == null) {
          currentNode.childRight = nodeToAdd;
          return tree;
        }
        else {
          return insert(tree, nodeToAdd, currentNode.childRight);
        }
      }
    }
  }

  public class Tree {
    public IntNode root;
    public Tree(IntNode root) {
      this.root = root;
    }

    public void InsertRawNode(IntNode nodeToAdd, IntNode currentNode = null) {
      if (currentNode == null) {
        currentNode = root;
      }

      if (currentNode.value >= nodeToAdd.value) {
        if (currentNode.childLeft == null) {
          currentNode.childLeft = nodeToAdd;
        }
        else {
          InsertRawNode(nodeToAdd, currentNode.childLeft);
        }
      }
      else {  //(currentNode.value < nodeToAdd.value)
        if (currentNode.childRight == null) {
          currentNode.childRight = nodeToAdd;
        }
        else {
         InsertRawNode(nodeToAdd, currentNode.childRight);
        }
      }
    }

    public void InsertInt(int number, IntNode currentNode = null) {
      if (currentNode == null) {
        currentNode = root;
      }

      if (currentNode.value > number) {
        if (currentNode.childLeft == null) {
          currentNode.childLeft = new IntNode(number, currentNode);
        }
        else {
          InsertInt(number, currentNode.childLeft);
        }
      }
      else if (currentNode.value != number){  //(currentNode.value < nodeToAdd.value)
        if (currentNode.childRight == null) {
          currentNode.childRight = new IntNode(number, currentNode);
        }
        else {
          InsertInt(number, currentNode.childRight);
        }
      }else {
        Console.WriteLine("NO DUPLICATES YOU KNOB");
      }
    }

    public int getDepth(int number, IntNode currentNode = null, int depth = 0) {
      if (currentNode == null) {
        currentNode = root;
      }

      if (currentNode == null) {
        return -1;
      }
      else if (currentNode.value > number) {
        return getDepth(number, currentNode.childLeft, depth + 1);
      }
      else if (currentNode.value < number) {
        return getDepth(number, currentNode.childRight, depth + 1);
      }
      else {  // (currentNode.value == number)
        return depth;
      }
    }

    public List<string> printFuckingEverything(List<string> result = null, IntNode currentNode = null) {
      if (currentNode == null) {
        currentNode = root;
      }
      if (result == null) {
        result = new List<string>();
      }
      string toCheck = getDepth(currentNode.value).ToString() + ".";
      //I KNOW THIS IS UGLY AND SLOW BUT IndexOf doesnt work and neither does Contains for some bloody reason
      if (result.Count == 0) {
        result.Add(toCheck + " " + currentNode.value.ToString());
      }
      else if (result.Count > 0) {
        bool addValue = false;
        for (int i = 0; i <= result.Count - 1; i++) {
          addValue = false;
          if (result[i].Contains(toCheck)) {
            string direction;
            if (currentNode == currentNode.parent.childRight) {
              direction = "R";
            }
            else {
              direction = "L";
            }
            result[i] += " " + currentNode.value.ToString() + direction + currentNode.parent.value.ToString();
          }else {
            addValue = true;
          }
        }

        if (addValue) {
          string direction;
          if (currentNode == currentNode.parent.childRight) {
            direction = "R";
          }
          else {
            direction = "L";
          }
          result.Add(toCheck + " " + currentNode.value.ToString() + direction + currentNode.parent.value.ToString());
        }
      }

      if (currentNode.childLeft != null) {
        printFuckingEverything(result, currentNode.childLeft);
      }
      if (currentNode.childRight != null) {
        printFuckingEverything(result, currentNode.childRight);
      }
      return result;

    }

  }

  public class IntNode {
    public int value;
    public IntNode childLeft, childRight, parent;
    public IntNode(int value, IntNode parent) {
      this.value = value;
      this.parent = parent;
      childLeft = null;
      childRight = null;
    }
    public void setLeftC(IntNode node) {
      childLeft = node;
    }
    public void setRightC(IntNode node) {
      childRight = node;
    }
  }
}