Sum of ranks in a binary tree - is there a better way

Question

Maybe this question does not belong as this is not a programming question per se, and i do apologize if this is the case.

I just had an exam in abstract data structures, and there was this question:

the rank of a tree node is defined like this: if you are the root of the tree, your rank is 0. Otherwise, your rank is the rank of your parents + 1.

Design an algorithm that calculates the sum of the ranks of all nodes in a binary tree. What is the runtime of your algorithm?

My answer I believe solves this question, my psuedo-code is as such:

int sum_of_tree_ranks(tree node x)
{
    if x is a leaf return rank(x)
    else, return sum_of_tree_ranks(x->left_child)+sum_of_tree_ranks(x->right_child)+rank(x)
}

where the function rank is

int rank(tree node x)
{
    if x->parent=null return 0
    else return 1+rank(x->parent)
}

it's very simple, the sum of ranks of a tree is the sum of the left subtree+sum of the right subtree + rank of the root.

The runtime of this algorithm I believe is n^2. i believe this is the case because we were not given the binary tree is balanced. it could be that there are n numbers in the tree but also n different "levels", as in, the tree looks like a linked list rather than a tree. so to calculate the rank of a leaf, potentially we go n steps up. the father of the leaf will be n-1 steps up etc...so thats n+(n-1)+(n-2)+...+1+0=O(n^2)

My question is, is this correct? does my algorithm solve the problem? is my analysis of the runtime correct? and most importantly, is there a better solution to solve this, that does not run in n^2?

Answer 1

Your algorithm works. your analysis is correct. The problem can be solved in O(n) time: (take care of leaves by yourself)

int rank(tree node x, int r)
{
    if x is a leaf return r
    else
        return rank(x->left_child, r + 1)+ ranks(x->right_child, r + 1) + r
}
rank(tree->root, 0)