Counting the number of Nodes in Binary Tree O(logn)^2

Question

I have a question in which I need to find the number of nodes in a complete tree in time complexity of
O((log(n))^2) e.g. (log of n )^2 , my go was
to find h which is h= log n (the height of the tree, moving always left as it is a complete tree) and then come to each node at h-1 and check if it has a right node, if it has, then it must have a left node (because of complete tree) if it doesn't then check if it has a left node and just like that count the number of nodes.

The problem is that I think it is O(n) because h = log(n) and the number of nodes in this height is 2^(h-1) and so this whole process is O(n) and not O( (log n)^2) ..

The output of

is 12 as it has 12 nodes , in time complexity of O( (log n)^2)

I would appreciate help please! thank you.

Answer 1

First, count the distance to the leftmost leaf by traversing left pointers. Then do the same with right pointers. If both numbers are n, then you have a perfect tree with 2^n - 1 nodes.

Otherwise, they're not equal. Then the first count was some number n+1 and the second was n. We need to probe - with binary search as others have said - the complete n-deep layer of nodes (counting the root as layer 1) to find the leftmost that has either 0 or 1 children. There are 2^(n-1) nodes to probe. In the example, n=3, so we're probing 4 nodes.

We can probe that layer by considering the bits in the numbers 0..2^(n-1) - 1. In the example, this is 0..3 (which is n-2 bits). In a traversal from root to leaf, a 0 bit means "go left." A 1 means "go right." For a reason discussed below, you want to use the bits from highest to lowest-order (in the example, bits 1,0) from root toward leaves. It's not hard to see that using 0..2^(n-1) - 1 as path traversal "instructions," you'll get to every vertex in that layer from left to right. For example, 2 has bits 10. That means start at the root, go right then left, which takes you to F.

But of course you don't want to search each vertex in the n-deep layer, since that would make your search O(n). Instead, use binary search. First try the "instruction" at the midpoint of [0..2^(n-1) - 1]. If you find 2 children, then reduce the search bracket to values greater than the midpoint. If you find 0 children, then values less. Continue in this manner until you've either found a node with 1 child or the bracket is size 1 and there are 0 children. The latter means you've found the leftmost node in the layer with no children.

Now we can find the total number of children easily. The part of the tree down to layer n has 2^(n-1) - 1 nodes, and the "instruction" that got you to the final search node tells you how many nodes there are in layer n+1. Together, these tell you the final answer. I'll let you work out the final details.

Answer 2

As Michael told you have to somehow to apply binary search in your problem. So the easiest way to do it to go by this algorythm:

1. First, as you said, we have to find the height of a tree, to do this we just go streight to leftmost node;

2. As we know the height H of the tree, now we can apply the binary search:

3. I'll describe the algorythm for the root, which is the same for every next node:

   Every time we search the most left leaf of the right subtree.

   So if there is a leaf on the height H, as in the picture, then repeat procedure with the right child(find the left most leaf of the right subtree of the tree where "root" is Node C).

   If there is no leaf, then repeat the same procedure with left child of the root.

As we see, every time we cut the problem by the factor of 2. So the complexity would be H * (amount of searches) = log n * log n