Check if the tree is perfectly balanced?

Question

C++ / C#

Hello, there is a program that implements a binary search tree, you need to check if the tree is perfectly balanced. Help me figure out at least with an approximate verification algorithm.

/*//////////////////////////////////////////
** Построить бинарное дерево поиска, данными в узлах которого являются целые числа.
** Проверить, является ли полученное дерево идеально сбалансированным.
** Обойти дерево в прямом и симметричном порядке.
**
** Реализация дерева – по выбору студента (выбор обосновать!)
** Все структуры данных оформить в виде классов. Все данные считывать из файлов
*///////////////////////////////////////////
#include <iostream>

using namespace std;

struct Node
{
      int data;
      int height_left, height_right;
      Node * left, * right;
};

typedef struct Node *tree;

struct Node * NewNode (int data)       //создание нового узла
{
     struct Node * pTree = new Node;
     pTree->data = data;
     pTree->height_left = pTree->height_right =  0;
     pTree->left = pTree->right = NULL;
     return pTree;
}

/*
** Добавление данных в  дерево
*/
int AddNode (tree & pTree, int data)  //функция добавления узла в дерево, возвращается 1, если увеличивается высота дерева
{
    /* Если указатель равен нулю */
    if (!pTree)
    {
        pTree = NewNode(data);
        return 1;
    }

    /* Если добавляемый элемент уже существует */
    if (data == pTree->data)
        return 0;

    /* Добавление в левое поддерево */
    if (data < pTree->data)
    {
       if (AddNode(pTree->left,data))
       {
          pTree->height_left++;

          if (pTree->height_left > pTree->height_right)
            return 1;
       }
       return 0;
    }

    /* Добавление в правое поддерево */
    if (AddNode(pTree->right,data))
    {
       pTree->height_right++;

       if (pTree->height_right > pTree->height_left)
        return 1;
    }

    return 0;
}

/*
** Обход  и печать в  симметричном  порядке
*/
void PrintSim(tree pTree)
{
    if (pTree)
    {
        PrintSim(pTree->left);
        cout << pTree->data << '(' << pTree->height_left << '/' << pTree->height_right << ")  ";//значение узла (высота левого поддерева/высота правого поддерева)
        PrintSim(pTree->right);
    }
}

/*
** Обход  и печать в  прямом порядке
*/
void PrintPre(tree pTree)
{
    if (pTree)
    {
        cout << pTree->data << '(' << pTree->height_left << '/' << pTree->height_right << ")  ";//значение узла (высота левого поддерева/высота правого поддерева)
        PrintPre(pTree->left);
        PrintPre(pTree->right);
    }
}

/*
** Удаление дерева
*/
void DelTree(tree pTree)
{
     if (pTree->left)
        DelTree(pTree->left);

     if (pTree->right)
        DelTree(pTree->right);

     delete pTree;
}

int main()
{
    tree pTree = NULL;
    int mas[15]={14, 8, 1, 13, 7, 12, 6, 2, 9, 0, 11, 10, 4, 3, 5}, i;

    for (i = 0; i < 15; i++)
        AddNode(pTree, mas[i]);

    cout << "Обход Дерева в симметричном порядке" << endl;
    PrintSim(pTree);

    cout << endl << "Обход Дерева в прямом порядке" << endl;
    PrintPre(pTree);

    DelTree(pTree);

    return 0;
}

Answer 1

With a symmetrical traversal, when you reach the end of the left subtree, you return the depth to its parent (it will be 1), then you bypass the right one and return its depth. Returning one level up, you return as depth the maximum value from the left and right depths, as the depth for the left / right subtree. In parallel, you check if, after traversing the right subtree, the depths differ by more than 1, then you complete the algorithm and say that the tree is not balanced.