# Coding Interviews Problem 11: Counts nodes in Complete Binary Tree [Amazon]

# Problem

This problem was asked by Amazon.

Given a complete binary tree, count the number of nodes in faster than O(n) time. Recall that a complete binary tree has every level filled except the last, and the nodes in the last level are filled starting from the left.

# Solution

If we didn’t have any time restrictions, we could just go to every node and keep track of the count. But that doesn’t work since the solution would be linear time. We need to go faster. Look at the following image with trees to see the common types of trees.

Now that we understand trees, how do we get faster?

If you look at the thread about how to solve most tree questions (

https://codinginterviewsmadesimple.substack.com/p/ways-to-solve-most-tree-question/comments) you will see the following breakdown for a generic tree solution:

`def treeFunc(root, **other params):`

if(root==null):

return baseCase/other relevant params

val=operation(treeFunc(root.left), treeFunc(root.right))

return val

How does this apply to our question/solution? We know that the number of nodes in a tree= root + number of nodes(root.left) + number of nodes(root.right). See how we can fit that into our template? Now we go onto the next steps.

# Using what we got

Remember we are given a specific condition. Our input is always a **complete binary tree. **This also means that we are given some conditions that we can use. A complete binary tree can split into two distinct sub-trees. One of these trees is guaranteed to be full. The other may be full (we have a full tree). Or we have another complete binary tree. See the magic?

We can keep cutting out the subtrees that are not full in logarithmic time. Eventually, we will get to the last layer, where we can count directly. And what about the full binary (sub)trees? That’s where we use some math.

For a full tree, the depth to the leftmost node is the same as the depth to the rightmost node, and the number of nodes is *2^(**depth+1)*

. In other words, in this case, using only two O(h) operations, we can calculate the total number of nodes. As a result, whenever we find a complete subtree, we can calculate its node count directly and stop recursing. And because this is a complete tree, it must be the case that either the left or right subtree (or both) is full, at each level. In this way, we will only need to analyze half the tree at each depth.*- 1*

And what of the not full binary trees? Simple we can just…

split them. Since we have the property that the subtree will split into a full and complete (sub)sub-tree. We can keep calculating the trees using the following code:

`def find_left_height(root):`

height = 0

while root.left:

root = root.left

height += 1

return height

def find_right_height(root):

height = 0

while root.right:

root = root.right

height += 1

return height

def count_nodes(root):

if not root:

return 0

left = find_left_height(root)

right = find_right_height(root)

if left == right: #(sub)tree is full

return (2 << left) - 1

else:

return count_nodes(root.left) + count_nodes(root.right) + 1

Sketch through a few examples to convince yourself why this would work. Otherwise, just reach out to me for an explanation.

What about time complexity? At each level of the tree we make a constant number of `O(h)`

calls, where `h`

is the depth at that level. So our time complexity is `O(h + (h - 1) + ... + 0)`

= `O(h^2)`

= `O((log N)2)`

.

** Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at** ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources.

**20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!**

Using this discount will drop the prices-

*800 INR (10 USD) → 640 INR (8 USD) per Month*

*8000 INR (100 USD) → 6400INR (80 USD) per year (533 INR /month)*

# Reach out to me

Use the links below to check out my other content, learn more about tutoring, reach out to me about projects, or just to say hi.

Small Snippets about Tech, AI and Machine Learning over here

AI Newsletter- https://artificialintelligencemadesimple.substack.com/

My grandma’s favorite Tech Newsletter- https://codinginterviewsmadesimple.substack.com/

Check out my other articles on Medium. : https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Reach out to me on LinkedIn. Let’s connect: https://rb.gy/m5ok2y

My Instagram: https://rb.gy/gmvuy9

My Twitter: https://twitter.com/Machine01776819