[Solution]Problem 85: Count Complete Tree Nodes [Amazon]

Recursion, Trees, Data Structures.

Hey, it’s your favorite cult leader here 🐱‍👤

On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those coding/tech/software engineering Interviews. 🔥🔥💹💹

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

p.s. you can learn more about the paid plan here.

---

Don’t know if you heard, but there was a very explosive publication at Google that got leaked saying some fairly spicy things about Language Models and AI.

But the uncomfortable truth is, we aren’t positioned to win this arms race and neither is OpenAI. While we’ve been squabbling, a third faction has been quietly eating our lunch. I’m talking, of course, about open source. Plainly put, they are lapping us.

-One of the quotes from this document

Naturally, we will be covering all of this in great detail in upcoming articles. In the meanwhile, if you’d like to discuss the outcomes with me, I’d love to hear your thoughts on the LinkedIn post here. Now let’s get back to the solution. Make sure you read this one through to the very end.

You can find it as 222. Count Complete Tree Nodes on Leetcode.

Problem

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 5 * 104].

• 0 <= Node.val <= 5 * 104

• The tree is guaranteed to be complete.

Try the Solution for yourself here

Step 1: Brute force

Notice that this problem is relatively straightforward in its setup and what it asks. It’s also asking you about a Binary Tree, one of the most common data structures. In your interview setting So to save time, it is prudent to skip the usual exploration phase and start exploring the mechanics of the problem. To do so, we pull out our handy old buddy- the brute force 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.

Image Source

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

Let’s go back to the recursive nature of the trees. Almost 2 years ago, I did a post covering how you could solve most Binary Tree Problems by using a particular template that I covered here (fun fact you can extend it to recursive structures in general, try to figure out how). So we take the template-

def treeFunc(root, **other params):
    if(root==null):
        return baseCase/other relevant params
    val=operation(treeFunc(root.left), treeFunc(root.right))
    return val

And use it for our solution. How do you ask?

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. It’s time to optimize our solution

Step 2: Optimizing

There is an easy trick to allow you to optimize most code. It’s something I use all the time in solutions. Think about what it is, before proceeding.

Brute force solutions are slow because they are …brutish. The way to get around that is to leverage the specific details of our problems.

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. This means that 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…

Think about this. Don’t scroll without having an answer.

Or at least an attempted solution.

We split them. Since we have the property that the subtree will split into a full and complete (sub)sub-tree. So we can apply the recursive leap of faith (read more about this here) to “Conceive, Believe and Achieve” our way to glory

Step 3 Coding It Up

Once we have all the mechanics figured out, the rest becomes easy.

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        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
        return count_nodes(root)

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).

Space Complexity- O(1) extra space needed. If you want brownie points, you can mention the extra space needed by the function calls. How much will that be? Think for a second, it’s not super difficult. Make sure you mention that in reality, many computers are now optimized for recursion- so costs would be lower than this limit.

Before you go- as you may have seen yesterday- we are done with the weekly Leetcode solutions. This might seem off to some of you since many people here subscribed for the Leetcode improvement. However, don’t feel bad about it. You will still have access to the old solutions. And as I mentioned yesterday, if you struggle with a question- you can always message me. I will cover that question + solution in the newsletter- just like I do now.

So why am I making this change? At this point- I’ve done the most meaningful solutions. Once you’ve developed templates and patterns for meaningful solutions (questions that show up a lot), you are left with 2 things-

1. Do more niche questions. This would defeat the purpose and just overwhelm you. These questions would most likely hurt your performance since they are by their nature esoteric and thus don’t fall into patterns. This would be great if you wanted to become a competitive coder, but you’re here to pass interviews. The focus has always been on the best ROI- so that you can ace 90% of your interviews by studying a few hours a week.

2. Repeat Questions/Similar Questions- I could keep hitting you with more of the same type of questions, but I think the utility of such a thing goes down after a while. I’d get bored writing, and you’d get bored reading the same things.

Once again, if you struggle with any questions- you can always message me. I will cover it (either for you privately or in this newsletter, based on the question). If you’ve been here a while, thank you for all the kind things you said about my writing as I got started. It’s thanks to those words I stuck to this: even though writing and social media can be very soul-sucking at times. Your support has been much appreciated. We’ve got really fun plans coming up, so stay tuned.

Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke,

Go kill all,

Devansh <3

Reach out to me on:

Small Snippets about Tech, AI and Machine Learning over here

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

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