Depression is a common and serious medical disorder that negatively affects the mood and the emotions of people, especially adolescents. In this paper, a novel framework for automatically creating Fuzzy Cognitive Maps (FCMs) is proposed. It is applied for the estimation of the severity of depression among adolescents, based on their electroencephalogram (EEG). The introduced Constructive FCM (CFCM) utilizes features extracted by a Constructive Fuzzy Representation Model (CFRM), which conduces to detect in a more intuitive way the cause-and-effect relationships between the brain activity and depression. CFCM contributes to limiting the participation of experts, and the manual interventions in the traditional construction of FCMs, it provides an embedded mechanism for dimensionality reduction, and it constitutes an inherently interpretable approach to decision making, while being uncertainty-aware and simple to implement. The results of the experiments, using a recent publicly available dataset, demonstrate the effectiveness of the proposed framework and highlight its advantages.