class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
/**
the left node is less than the root. 
the right node is more than the root. 
**/
function insert(root, val) {
  const node = new Node(val);
  if (root == null) {
    return node;
  }

  let lcur = root;
  while (true) {
    if (val > lcur.data) {
      if (lcur.right) {
        lcur = lcur.right;
        continue;
      } else {
        lcur.right = node;
        return root;
      }
    } else if (val <= lcur.data) {
      if (lcur.left) {
        lcur = lcur.left;
        continue;
      } else {
        lcur.left = node;
        return root;
      }
    }
  }
  return root;
}

function visit(node, arr) {
  arr.push(node.data);
}

// By inorder traversal
function print(root, arr = []) {
  if (root == null) {
    return root;
  }
  print(root.left, arr);
  visit(root, arr);
  print(root.right, arr);

  return arr;
}

function findMinNode(root) {
  let temp = root;

  while (temp.left) {
    temp = temp.left;
  }

  return temp;
}

// O(h) /// h = hight
function find(root, data) {
  if (root == null) {
    return root;
  }
  if (root.data === data) {
    return root;
  }
  if (data > root.data) {
    return find(root.right, data);
  } else if (data < root.data) {
    return find(root.left, data);
  }
}

/*
Implement an algorithm to get successor of a node.
*/
function getSuccessor(root, data) {
  /**
  case 1: if node has right subtree, then find the min node.  */
  //O(h)
  /*Case 2: If not has no right subtree, then find the nearest ancestor node for which current node is in left subtree..
   */
}

// unit tests
// do not modify the below code
describe("Given that you have a Binary Search Tree Write algorithm to find the inorder successor of a given node", function () {
  it("should remove correctly", () => {
    let arr = [];
    let root = null;
    [7, 4, 9, 1, 6].forEach((a) => {
      root = insert(root, a);
    });

    expect(print(root)).toEqual([1, 4, 6, 7, 9]);
    expect(print(getSuccessor(root, 4))).toEqual([6]);
  });

  it("should remove correctly", () => {
    let arr = [];
    let root = null;
    [3, 7, 4, 6, 5, 1, 10, 2, 9, 8].forEach((a) => {
      root = insert(root, a);
    });

    expect(print(root)).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    expect(print(getSuccessor(root, 4))).toEqual([5]);
  });
});