Как я могу найти количество узлов, которые меньше или равны заданному значению в BST? (AVL TREE)

Question

, поэтому мне нужно написать рекурсивную функцию, которая получает корень BST, и другой параметр, который равен k, и мне нужно найти количество узлов, которые меньше или равны k в BST. Есть идеи? Спасибо Я попробовал эту функцию, но она действительно не работала (работала только для самых маленьких 5 узлов в дереве)

int avl_rank( AVLNodePtr tnode, int k )

if (tnode == NULL)
    return 0;

int count = 0;

// if current root is smaller or equal
// to x increment count
if (tnode->key <= k)
    count++;

// Number of children of root
int numChildren;
if (tnode->child[0]==NULL && tnode->child[0]==NULL)
    numChildren = 0;
else if ((tnode->child[0]!=NULL && tnode->child[0]==NULL) || (tnode->child[0]==NULL && tnode->child[0]!=NULL))
    numChildren = 1;
else numChildren = 2;

// recursively calling for every child
int i;
for ( i = 0; i < numChildren; i++)
{
    AVLNodePtr child = tnode->child[i];
    count += avl_rank(child, k);
}

// return the count
return count;

}

Answer 1

int avl_rank( AVLNodePtr tnode, int k )
{
    if(tnode==NULL) return 0;
    int count = 0;
    if (tnode->key<=k) count++;
        count += (avl_rank(tnode->child[0],k) +
            avl_rank(tnode->child[1],k));
    return count;
}