Нужно найти количество листьев сбалансированного дерева

Поиск листьев дерева в функции search. В моем примере выводит элемент 2, который не является листом дерева

    #include <iostream>

    using namespace std;

    struct tree
    {
        int info;
        tree* left;
        tree* right;
    };

    tree* addTree(int a, int n, int* mas)
    {
        tree* temp;
        int m;

        if (a > n)
            return nullptr;

        m = (a + n) / 2;

        temp = new tree;
        temp->info = mas[m];

        temp->left = addTree(a, m - 1, mas);
        temp->right = addTree(m + 1, n, mas);

        return temp;
    }

    void showTree(tree* temp)
    {
        if (!temp)
            return;

        showTree(temp->left);

        cout << temp->info << " ";

        showTree(temp->right);
    }

    void delTree(tree* temp)
    {
        if (!temp)
            return;

        delTree(temp->left);
        delTree(temp->right);
        delete temp;
        return;
    }

    void search(tree* temp)
    {
        if (!temp)
            return;

        search(temp->left);

        if ((temp->left == nullptr) && (temp->right == nullptr))
            cout << temp->info << " ";

        search(temp->right);
    }

    int main()
    {
        setlocale(LC_ALL, "Russian");

        int n;
        int mas[20];
        tree* root = nullptr;

        cout << "Введите количество элементов в дереве: ";
        cin >> n;
        cout << endl;

        for (int i = 0; i < n; i++)
        {
            cin >> mas[i];
        }

        for (int step = n / 2; step > 0; step /= 2)
        {
            for (int i = 0; i < n; i += step)
            {
                for (int j = i + step; j < n; j += step)
                {
                    if (mas[i] > mas[j])
                    {
                        int temp = mas[i];
                        mas[i] = mas[j];
                        mas[j] = temp;
                    }
                }
            }
        }

        root = addTree(0,  n - 1, mas);

        cout << endl << endl;

        cout << "Элементы в дереве: " << endl;
        showTree(root);
        cout << endl << endl;

        cout << "Листья дерева: " << endl;
        search(root);

        delTree(root);
        return 0;
    }