Leetcode 222 Count Complete Tree Nodes Python Typescript

00:00 Introduction
00:15 Analysis
02:58 Demo
05:55 Code

Demo: https://ericwebsmith.github.io/leetcode_web/?id=222

Subtitle:

Hi, Everyone.
Let's look at Today's Leetcode daily 222 Count Complete Tree Nodes.
In this problem,
We are given a complete tree.
And we'll count the nodes.
We know that in a non-complete tree,
If we want to know how many nodes are there,
we will use in-order, pre-order, post-order or level order to
travel each of the nodes
before we can know the count.
Since we've traveled every node,
the time complexity is O(n).
But the problem said that
we have to find a solution
that is better than O(n).
When I was looking as this complete tree,
I hoped that this complete was perfect.
Like that.
So that I will be easy to count the number of nodes
using the following equation.
that is 2 to the power of h minus 1.
h is the height, here h is 4.
So 2 to the power of 4 is 16.
16 minus 1 is 15.
We can see we have 15 nodes here.
However, a complete tree is not necessary a perfect tree.
But if we look at this complete tree closely,
we can see that at least
one of its sub tree is perfect.
It is either the left tree or the right tree.
Because, we can see this left tree is perfect, right?
If we make this left tree non-perfect tree.
than the right tree will be perfect.
Because if we want to make this left tree non-perfect,
we have to at least remove 11.
But if we want to remove 11,
we have to remove each of the nodes after 11.
So this will make the right tree perfect.
So that we will know,
in a complete tree,
One of the sub-tree is perfect.
here we can use divide and conquer
to divide this problem into sub problems
of counting the nodes of the sub-trees.
let me demonstrate.
Firstly, we'll count from the root to the left to the left and until the last.
Now we can see the left height is 4.
But the right height is 3.
So the height is different.
This means this tree is not perfect.
But we can then count the nodes of the sub-trees.
We'll firstly count the left sub-tree.
The left sub-tree has the same height for the leftmost and the rightmost.
So this sub-tree is perfect.
We know we can use this equation.
here,
2 to the power of 3 minus 1.
that is 8 minus 1.
So we have 7 here, right?
1, 2, 3, 4, 5, 6, 7.
We have 7 nodes here.
right?
Now for the right part.
Still they are not perfect.
And it is not perfect.
We'll count them one by one.
Until we find that the left part has 4 nodes.
Now we just add 4 and 7 and this one.
this will make up 12 nodes.
this is the Python code and typescript code.
If you like this video, please give me a thumb up.
Thank you.