class BinarySearchTree {
  constructor(key=null, value=null, parent=null) {
    this.key = key;
    this.value = value;
    this.parent = parent;
    this.left = null;
    this.right = null;
  }

  insert(key, value) {
    if (this.key === null) {
      this.key = key;
      this.value = value;
    }
    else if (key < this.key) {
      if (this.left === null) {
        this.left = new BinarySearchTree(key, value, this);
      }
      else {
        this.left.insert(key, value);
      }
    }
    else {
      if (this.right === null) {
        this.right = new BinarySearchTree(key, value, this);
      }
      else {
        this.right.insert(key, value);
      }
    }
  }

  get(key) {
    if (this.key === key) {
      return this.value;
    }
    else if (key < this.key && this.left) {
      return this.left.get(key);
    }
    else if (key > this.key && this.right) {
      return this.right.get(key);
    }
    else {
      throw new Error('Key Error');
    }
  }

  remove(key) {
    if (this.key === key) {
      if (this.left && this.right) {
        const successor = this.right._findMin();
        this.key = successor.key;
        this.value = successor.value;
        successor.remove(successor.key);
      }
      else if (this.left) {
        this._replaceWith(this.left);
      }
      else if (this.right) {
        this._replaceWith(this.right);
      }
      else {
        this._replaceWith(null);
      }
    }
    else if (key < this.key && this.left) {
      this.left.remove(key);
    }
    else if (key > this.key && this.right) {
      this.right.remove(key);
    }
    else {
      throw new Error('Key Error');
    }
  }
// IF 15 has a parent
// If 15 is to the left of the parent, then point 15's parent left pointer to node,
// If 15 is to the right of the parent, then point 15's parent right pointer to node.

// Make the Parent of the node, the parent of the one we replaced.

// else its the root node.

  _replaceWith(node) {
    if (this.parent) {
      if (this == this.parent.left) {
        this.parent.left = node;
      }
      else if (this == this.parent.right) {
        this.parent.right = node;
      }

      if (node) {
        node.parent = this.parent;
      }
    }
    else {
      if (node) {
        this.key = node.key;
        this.value = node.value;
        this.left = node.left;
        this.right = node.right;
      }
      else {
        this.key = null;
        this.value = null;
        this.left = null;
        this.right = null;
      }
    }
  }

  _findMin() {
    if (!this.left) {
      return this;
    }
    return this.left._findMin();
  }
}




let myTree = new BinarySearchTree;

//E A S Y Q U E S T I O N
//              E
//           S     A
//        Y   S  E
//          Q  I
//        U   O
//          T   N

myTree.insert('E');
myTree.insert('A');
myTree.insert('S');
myTree.insert('Y');
myTree.insert('Q');
myTree.insert('U');
myTree.insert('E');
myTree.insert('S');
myTree.insert('T');
myTree.insert('I');
myTree.insert('O');
myTree.insert('N');

// console.log(myTree);

//Write an algorithm to find the height of a binary search tree

let myTree2 = new BinarySearchTree;

myTree2.insert(10);
myTree2.insert(5);
myTree2.insert(13);
myTree2.insert(7);
myTree2.insert(14);
myTree2.insert(12);
myTree2.insert(3);
myTree2.insert(15);




function findHeight(tree) {


  if(tree.left && tree.right) {

    return Math.max(findHeight(tree.left), findHeight(tree.right)) + 1;
  }
  if(tree.left) {

    return findHeight(tree.left) + 1;
  }
  if(tree.right) {

    return findHeight(tree.right) + 1;
  }

  return 1;
}



// console.log(findHeight(myTree2));

// take 2
function getHeight(tree){
  return Math.max(tree.left && getHeight(tree.left), tree.right && getHeight(tree.right)) + 1;
}

// console.log(getHeight(myTree2));
// take 3
function bst_height(tree) {
  if(tree.left && tree.right) return Math.max(bst_height(tree.left), bst_height(tree.right)) + 1;
  if(tree.left) return bst_height(tree.left) + 1;
  if(tree.right) return bst_height(tree.right) + 1;

  return 1;
}

// console.log(bst_height(myTree2));
// Write an algorithm to check whether an arbitrary binary tree is a binary search tree, assuming the tree does not contain duplicates

//if this.left > current key then return false
////if this.right < current key then return false
//


// take 2 is_bst?
function is_bst(tree) {

  if((tree.left === undefined) || (tree.right === undefined)) return false;

  if(tree.children > 2) {
    return false;
  }

  if(tree.left) {
    if(tree.left.key > tree.key) return false;
    if(!is_bst(tree.left)) return false;
  }

  if(tree.right) {
    if(tree.right.key < tree.key) return false;
    if(!is_bst(tree.right)) return false;
  }

  return true;
}

console.log(is_bst(myTree2));