Time and space complexity of this algorithm for counting nodes in a complete binary tree

Question

I have this below code for calculating the number of nodes in a complete binary tree^* without visiting all the nodes.

    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int LH=height(root,false); // depth of leftmost leaf
        int RH=height(root,true);  // depth of rightmost leaf
        if(LH==RH){
            return (int)Math.pow(2,LH)-1;
        }
        else return countNodes(root.left)+countNodes(root.right)+1;
    }

    int height(TreeNode root,boolean lr){
        if(root==null)
            return 0;
        if(lr==false)
            return 1+height(root.left,lr);
        return 1+height(root.right,lr);
    }

How can I determine the time complexity here? I'm confused the nodes are visited more than once.

---

_{^*Complete binary tree: all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible}

Answer 1

Your height function follows a single path from the current node to a single leaf (either the leftmost, or the rightmost leaf). This has a time complexity of O(ℎ) where ℎ is the height of that node.

When recursion of countNodes is needed (because the leftmost leaf is deeper than the rightmost leaf), then we know that in at most one of the two recursive calls of countNodes this situation will occur again, i.e. where the leftmost leaf is deeper than the rightmost leaf.

So in the worst case the recursive calls of countNodes will deepen all the way to a leaf. All other recursive calls of countNodes will hit the base case immediately (as there LH and RH are equal), and those represent two more calls of height that can be considered work that is part of the work that was done for the parent node. This way we account for work only on a single path from the root to a leaf.

So taking this all together we have O(1 + 2 + 3 + 4 + ... + log𝑛). This is a triangular number, and thus we have O(log𝑛(1+log𝑛)/2) = O(log²𝑛).

The space complexity is trivial: each new variable that this code allocates takes constant space, so the recursion stack is the determining factor: O(log𝑛).