在O（1）时间中查找BST大小C

Question

我有两个问题。这两个函数的当前运行时是什么？如果不是O（1）（似乎对我来说像O（n）），有人可以给我一个提示（而不是给我答案）关于如何使其变为O（1）吗？谢谢

static int size(NODE *r)
{
    if(r==NULL) 
        return 0;

    return size(r->left) + size(r->right) + 1;
}


int bst_size(BST_PTR t)
{
    return size(t->root);
}

Answer 1

节点可以包含在BST struct中，该节点将具有一个计数器，该计数器在插入/删除时将增加和减少。