Function insertInSubtree(node, key, value):
  If node is null:
    return new BST_Node(key, value)
  If key == node.key:
    ERROR
  If key < node.key:
    node.left = insertInSubtree(node.left, key, value)
  If key > node.key:
    node.right = insertInSubtree(node.right, key, value)

  rebalance(node)

  node.height = max(node.left.height, node.right.height) + 1
  return node
End Function