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)- 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.
And what of the not full binary trees? Simple we can just…
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.