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