algorithm - Counting number of nodes in a complete binary tree -

i want count number of nodes in complete binary tree can think of traversing entire tree. o(n) algorithm n number of nodes in tree. efficient algorithm achieve this?

suppose start off walking down left , right spines of tree determine heights. we'll either find they're same, in case last row full, or we'll find they're different. if heights come same (say height h), know there 2^h - 1 nodes , we're done.

otherwise, heights must h+1 , h, respectively. know there @ least 2^h - 1 nodes, plus number of nodes in bottom layer of tree. question, then, how figure out. 1 way find rightmost node in last layer. if know @ index node is, know how many nodes in last layer, can add 2^h - 1 , you're done.

if have complete binary tree left height h+1, there between 1 , 2^h - 1 possible nodes in last layer. question how determine efficiently possible.

fortunately, since know nodes in last layer filled in left right, can use binary search try figure out last filled node in last layer is. essentially, guess index might be, walk root of tree down leaf should be, , either find node there (so know rightmost node in bottom layer either node or right) or don't (so know rightmost node in bottom layer must purely right of current location). can walk down kth node in bottom layer should using bits in number k guide search down: start @ root, go left if first bit of k 0 , right if first bit of k 1, use remaining bits in corresponding manner walk down tree. total number of times we'll o(h) , each probe takes time o(h), total work done here o(h²). since h height of tree, know h = o(log n), algorithm takes time o(log² n) time complete.

i'm not sure whether it's possible improve upon algorithm. can ω(log n) lower bound on correct algorithm, though. i'm going argue algorithm correct in cases must inspect rightmost leaf node in final row of tree. see why, suppose there's tree t algorithm doesn't this. let's suppose rightmost node algorithm inspects in bottom row x, actual rightmost node in bottom row y, , leftmost missing node in bottom row algorithm detected z. know x must left of y (because algorithm didn't inspect leftmost node in bottom row) , y must left of z (because y exists , z doesn't, z must further right y). if think algorithm's "knowledge" @ point, algorithm has no idea whether or not there nodes purely right of x or purely left of z. therefore, if give modified tree t' deleted y, algorithm wouldn't notice had changed , have same execution path on t , t'. however, since t , t' have different number of nodes, algorithm has wrong on @ least 1 of them. inspecting node takes time @ least ω(log n) because of time required walk down tree.

in short, can better o(n) above o(log² n)-time algorithm, , might able better that, though i'm not entirely sure how or whether that's possible. suspect isn't because suspect binary search optimal way check bottom row , lengths of paths down nodes you'd probe, after taking account share nodes in common, θ(log² n), i'm not sure how prove it.

hope helps!