'use strict';

function inOrderSuccessor(node) {
  if (!node) {
    return null;
  }

  if (node.right) {
    return leftMostChild(node.right);
  } else {
    var currentNode = node;
    // Assuming each node has a reference to its parent
    var parentNode = currentNode.parent;

    // Go up until we find deepest ancestor for which node would be in left sub tree
    while (parentNode && parentNode.left !== currentNode) {
      currentNode = parentNode;
      parentNode = parentNode.parent;
    }

    return parentNode;
  }
}

function leftMostChild(node) {
  if (!node) {
    return null;
  }
  while (node.left) {
    node = node.left;
  }
  return node;
}