L32. Count total Nodes in a COMPLETE Binary Tree | O(Log^2 N) Approach | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@bhaveshkumar6842]

Why is it return (1

[@g.upenderreddy]

@@bhaveshkumar6842 If you observe carefully there's change in height calculation root vs root.left or root.right public int countNodes(TreeNode root) { if (root == null) return 0; int leftHeight = leftHeight(root); int rightHeight = rightHeight(root); if (leftHeight == rightHeight) return (1

[@_PRANAYMATE]

@@g.upenderreddy You are right

[@abhishekanand5898]

This question was asked today in DUNZO round-1 and interviewer was expecting this approach

[@uRamPlus]

Self Notes: 🍇 Formula is (2^TreeLevel - 1). Only works for perfect tree. 🍇 To determine if its a perfect tree, go all the way down and count the nodes on left and right side, If they match, its a perfect tree and our formula applies. 🍇 If its not a perfect tree, we go on left and right subtree and again determine if they are perfect tree. 🍇 When we have our left and right heights, we do (1 + left + right) 🍇 If we reach null, return 0 🍇 C++ note: 1

[@MeenakshiSharma-bd3bu]

Thankyou for posting, this also helps in making a short and crisp notes!!

[@gandhijainamgunvantkumar6783]

Thanks for posting this I am also using your notes.

[@shikharbansal2942]

Keep posting!

[@shaikfahim1232]

Shukriya bhai

[@parthsalat]

The emoji's are lit 🔥

[@dhirenparekh2646]

Instead of using two function to find left height first and then right height. We can use a single while loop and iterate till both of the root are not NULL and increment h++. if both are NULL then make the bool full=true and break and if anyone of them is NULL then just break. if full is true then return 2^h-1 else return 1+left+right int countNodes(TreeNode* root) { if(root==NULL)return 0; TreeNode* node=root->left; TreeNode* node2=root->right; int h=1; bool full=false; while(1){ if(node==NULL && node2==NULL){ full=true;break; } if(node==NULL || node2==NULL){ break; } node=node->left,node2=node2->right; h++; } if(full){ return pow(2,h)-1; } else{ return 1+countNodes(root->left)+countNodes(root->right); } }

[@mrmani1700]

Nice man❤

[@rudrasharma8523]

This can also be a solution with Time Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because the function visits each node exactly once to count it, resulting in a linear traversal of the tree. Space Complexity: The space complexity is O(h), where h is the height of the tree. This is due to the recursive call stack that is used during the traversal. In the worst case, for a skewed tree (like a linked list), the height can be n, leading to O(n) space. In a balanced tree, the height would be log(n), resulting in O(log n) space. class Solution { public: int countNodes(TreeNode* root) { if(root==nullptr) return 0; int left = countNodes(root->left); int right = countNodes(root->right); return left + right + 1; } };

[@falgunitagadkar4097]

I went on to like this video when Striver asked for it at the end but found out that I already liked it (this is the first time I am watching this video). This is magic for Striver!!!

[@harisrashid0773]

Rather than finding height at every node we can pass left height and right height and in left recursion left height is equal to left height -1 and give call for right height and in right subtree right height is right height -1 and give call for left height only.

[@gouravkushwaha68]

My intuition before watching this video is normal traversing the tree from like BFS and while traversing take the count variable and increase the count by 1 if any node occurs while traversing the tree and then return count

[@bhaveshkumar6842]

Thank you so much Striver for your amazing content. You have helped me understand the concepts which I initially used to find too intimidating.

[@jayasuryam3976]

If anyone struck here , see this (2

[@AvikNayak_]

sukriya!!!

[@shashwatpriyadarshy7681]

Correction: While returning the number of nodes, in the video's solution we are returning (1

[@pranavsharma7479]

true

[@anishgupta7553]

You are wrong. You didn't understood code correctly because in code , he has already included root node in height

[@apurvsinha8793]

or you could just start with hght=1 in both left and right height traversals then the formula will not change

[@iampatelajeet]

Leetcode discussion section se pareshaan hoke aaya and you satisfied bro.. thank youuuuuu

[@rishabkumar4940]

This can also be done by binary searching on all the sizes possible. We have to check whether the size element is present in the tree or not. The complexity will be the same.

[@anshumansharma4580]

This can also be done by applying binary search in the last level. Getting to the last level will take logN time and binary Search itself will take logN time, so overall logN_wholeSquare time

[@your_name96]

checking whether the size element is present or not takes O(n) time for binary tree right?

[@KalingaAbhisek]

Just a correction to striver bhaiya's java code class Solution { public int countNodes(TreeNode root) { if(root==null) return 0; int left=ghl(root.left); int right=ghr(root.right); if(left==right) return (2

[@konpeeyush]

Thanks bro

[@mdrehankhan3458]

it should be (1

[@deepanshuaggarwal5181]

@@mdrehankhan3458 yes

[@Tanishq181]

Niceeee

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@ishanshah3309]

Very good explanation. I specially loved the explanation of Time complexity for this. I think no one clears TC in their videos apart from striver. so this clearing Time space complexities and clear explanation of solution gives him edge and makes him better than anyone teaching DSA

[@parthsalat]

It's uplifting to see children learn DSA at such a young age...

[@isheep9025]

Self note: why complexity is log2n, except for the last level every level needs to be compelty filled, so in the left side we might have to go till the last level finding a node whose left height and right height are similar which can be at max till approx logn level since complete is full execpt the last level ,and in every of those logn levels we came we must have computed height each of logn (since complete tree is filled execpt the last level) ->ogn*logn

[@aryanraj3413]

didn't understand why complexity is log2n

[@shivangmathur6112]

IN cpp code if (left height == right height) we need to (1

[@shashamnk2525]

why is that needed ? 1

[@shivangmathur6112]

@@shashamnk2525 that's how you calculate using bits 1 is represented as 00000000.......01 In binary 31 zeros then 1

[@shashamnk2525]

@@shivangmathur6112 I think we are calculating 2^h+1 because we are taking height of root as 0

[@naveenkumarjadi2915]

Great Explanation bro , thank you for this series

[@subramanyah9848]

One LIne Brute Force (Recursive) : 0(n) int countNodes(TreeNode root) { return (root == null)? 0 : 1 + countNodes(root.left) + countNodes(root.right); }

[@andr3w321]

I don't think the Time complexity analysis is correct for worst case runtime, but correct for average which was not explained. In best case: we're given a complete tree and traverse left and right side and return. O(2 * log N) ~ O(log N) In worse case: we're given a tree with all levels filled except last level only has one node. While we save some iterations on the right side, we are making repeated calls on the left side which more than makes up for it and worst case it degenerates to O(N). On average: Tree height: O(log N) Expected recursive calls: O(log N) Multiplicative: O((log N)^2) Time Complexity Summary: Best Case: O(log N) Worst Case: O(N) Average Case: O((log N)^2)

[@apmotivationakashparmar722]

Thank you so much for (logn*logn) approach.

[@sahilkhan_cs50]

📝Slightly different approach by not calculating the same nodes repeatedly for calculating the height.....We check the binary tree is faulty or not..By faulty I mean not prefect.If the tree rooted at root is faulty,then check its left and right sub trees .Any one of them will be faulty.The other will be the reverse.We can exploit this binary possibility in this way.If the left child tree is faulty,then dont recurse to the right side tree ,because the rght side tree is perfect and thus add the no of nodes acc. to the formula to the count passed as reference.If the left child tree is not faulty,i.e perfect then sum the nodes and recurse to the right child tree.This process goes on recursively .In this way,we leave many perfect subtrees and calculate the number of nodes without visiting them.And then we hit the base case where the tree is like / or . ...Then we return from there.We are not calculating repeatedly the heights again and again thus not repeteadly travelling the same nodes for finding the height...for the child trees the height will be that of parent-1 .for left child tree the left ht will be left ht of parent-1 and right ht we have to find....thus ensuring we are travelling the nodes only once ,not repeteadly.This further brings down the time.The complexity is O((logn)^2). class Solution { public: bool helper(TreeNode* root,int lh,int rh,int& count){ if(lh==rh) { count+=(1left; } helper(root->right,lhr,rh-1,count); count+=1; } return false; } int countNodes(TreeNode* root) { int lh=0,rh=0; TreeNode* node=root; while(node){ lh++; node=node->left; } node=root; while(node){ rh++; node=node->right; } int count=0; helper(root,lh,rh,count); return count; } };

[@rakshayadav1892]

Python code: class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: def rightheight(root): h=0 while root: h+=1 root=root.right return h def leftheight(root): h=0 while root: h+=1 root=root.left return h if leftheight(root)==rightheight(root): h=leftheight(root) return (2**h)-1 else: return 1+self.countNodes(root.left)+self.countNodes(root.right)

[@mayanksaurabhmayanksaurabh9271]

loved the thought process. Dry running it multiple really helped me grasp the concept. Good question using the properties of a specific type of tree.

[@paragroy5359]

Nice explanation your videos are really good...please keep on making such videos...you are doing a great job.

[@krishnavamsichinnapareddy]

Understood 👍 Time complexity explanation is really good

[@kavatishivakumar1733]

can u explain why time complexity logn^2?

[@sakshigupta7616]

Loved the video. You are the best! Keep going...

[@vedbhanushali608]

thank you sir great explanation.

[@MilindBasavaraja123]

Awesome Explanation. Leetcode solution was intimidating.

[@rishabhkumar8115]

Great explanation & crisp code just what striver do Great explanation & crisp code just what striver do

[@adebisisheriff159]

Thanks Striver

[@sharmanihal99]

Python Code for the same: class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root:return 0 left_depth=self.find_left_branch_depth(root) right_depth=self.find_right_branch_depth(root) if left_depth==right_depth: return (2**left_depth)-1 else: return 1+self.countNodes(root.left)+self.countNodes(root.right) def find_left_branch_depth(self, root): if not root:return 0 return self.find_left_branch_depth(root.left) + 1 def find_right_branch_depth(self, root): if not root:return 0 return self.find_right_branch_depth(root.right) + 1

[@AmitBiswas0142]

class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; return countNodes(root.left) + countNodes(root.right) + 1; } } Java code beats 100%

[@mayankkumar4864]

DOUBT : In C++ code why do we write (1

[@fundestroyer9281]

are dude 1

[@tankuharshida2855]

It's left shift operator so

[@DeadPoolx1712]

UNDERSTOOD;

[@harisrashid0773]

Loved it solved on my own

[@manasranjanmahapatra3729]

This nice intuition really liked it.

[@DurgaShiva7574]

Mauj kardi bhai ne.. 🔥🔥

[@sparshsharma6068]

Bhaiya, there is a typo in the java code, the while loop will have to execute till root != null but, in the code there was root.left and root.right in the two functions(We can also set the count initial value to 1, that will also work). At 13:17 , I got a bit confused on the part when you were explaining the calculation of the left height and the right height. I thought that the code won't work for the test case : 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 But then I dry ran the code and got to know that what you are actually doing is finding the depths of the rightmost and leftmost nodes of a given root. And then if you find that the depths are equal, we can thereby conclude that for the given root, the leftmost and the rightmost nodes are at the same level, and thus, by the definition of complete binary trees, we can further conclude that the tree is completely filled the complete binary tree. So, for the test case I mentioned above, for node 2, the depth of leftmost node (8) != the depth of rightmost node(5). So it will go on and check for the individual deeper nodes. Thus, the code will work fine.

[@kaushikramabhotla4635]

concluded well :)

[@sparshsharma6068]

@@kaushikramabhotla4635 Thanks 😊

[@naveen9646]

thanks clearing my doubt

[@ishantrivedi5588]

what if the tree is like this: 2 / \ 3 4 / \ / \ 3 5 9 10 / 6 then for left subtree of 2's height will be 3 and for right subtree of 2 it will also be 3 then it will calculate the nodes with the help of that formula which will give wrong result since it missed the last node (6).

[@BharatTheGreat1]

@@ishantrivedi5588 this is not a complete binary tree according to question given questions is always a complete binary tree

[@laveshgarg2189]

Great approach bhaiya maza aa gaya

[@Learnprogramming-q7f]

Thank you Bhaiya

[@oqant0424]

just a correction to bhaiya's cpp code: class Solution { private: int findHeightLeft(TreeNode* node){ int hgt=0; while(node){ hgt++; node=node->left; } return hgt; } int findHeightRight(TreeNode* node){ int hgt=0; while(node){ hgt++; node=node->right; } return hgt; } public: int countNodes(TreeNode* root) { if(!root)return NULL; int lh=findHeightLeft(root->left); int rh=findHeightRight(root->right); if(lh==rh)return (1right); } };

[@avyavsharma2994]

bro you're a savior been trying figure out for so long what was wrong with the code thanxxxxxx

[@cinime]

Understood! So fantastic explanation as always, thank you very much!!

[@nileshsinha7869]

Great explanation & crisp code just what striver do

[@adityapandey23]

Understood

[@abhijit-sarkar]

Time Complexity discussion at 13:40. You're welcome.

[@lavanyaprakashjampana933]

we love your content and we love you...🖤

[@AdityaKumar-be7hx]

Buddy, you are amazing!

[@someshpatel7660]

!!! IMP PLEASE REMEMBER : Here height of subtree is not exactly the subtree height, but here height (height term is bit confusing) calculation is the way to find out which subtree is perfect. i.e If the left boundary edges == right boundary edges. Dont confuse it with height

[@prajjwaldeepghosh7329]

Thank you

[@chiragbansod8252]

UNDERSTOOD

[@UECAshutoshKumar]

Thank you sir

[@hapysethi1306]

Thanks brother!

[@ASHISHKUMAR-jh9kw]

In JAVA code there should be ((1

[@sulthanmogal9692]

also i think..it shud be 1

[@gigachad2419]

Striver is Literally God for DSA.

[@rishabhgupta9846]

understood,awesome striver

[@rohitsm663]

Love you bhai

[@jk-sm6qr]

thanks

[@shastriamisha]

Great Great Explanation..Thank you

[@arijitdey8419]

great explanation as expected..thanks a lot for ur efforts

[@vrandakansal5940]

What a explanation...🙇‍♀️thanks a lot😅👍

[@mriduljain1981]

completed lecture 32 of free ka tree series.

[@raviraj-xq4ue]

bhai aise algo sochte kaise ho yaar ??? mtlb ki gazab

[@aryanyadav3926]

Amazing video!

[@ishanporwal4403]

i think the logic is somewhat broken as if in the first example there is left child of 6 then then lh=rh=4 would have held true....and we would have returned 2^4-1=15 but the ans is 12

[@harshitjaiswal9439]

understood

[@prateekjain7623]

you are superb sir

[@adityasaxena6971]

Great sirr

[@vrandakansal5940]

Greatt explanation....🙏🙏

[@budgetdapr]

Hi, Considering the subtrees of Node 2, if we remove the Node 11 from the right sub-tree, The height would still be 3. Am I getting it wrong?

[@subhasishkumbhakar1028]

NO, you are wrong. If we remove 11, it will not be same.

[@sayantaniguha8519]

Can we say that since this is an Almost Complete Binary Tree, which means the condition (leftHeight==rightHeight) will satisfy at-least once & not go wasted ?

[@tusharvlogs6333]

yeah . thats why we wont be traversing either the right or the left subtree once we find the height diference. one of the part has to satisfy this condition.

[@nagavedareddy5891]

Huge Respect...❤👏

[@TarunKumar-cn6in]

Thanks so much sir🙏

[@alesblaze4745]

thanks mate!

[@judgebot7353]

good algo

[@oqant0424]

understood!!!!!!!!!!!!!

[@tanishkumar6682]

understood

[@gowreeManohar]

got it sir thanks a lot

[@ashitapahwa7595]

i think in c++ code , it should be if(lh==rh) return (1

[@googiehammer]

your code is wrong and leetcode test cases are incomplete: why? because consider this test case [1,2,3,4,NULL,6,7]

[@avi7474]

practically, this method was .07 ms faster than the O(n) solution. Yeah nice.

[@deepakchawla1105]

thanks

[@dipanshut]

Understood!!

[@bhaveshkumar6842]

Why is it return (1

[@AB-iv4bq]

can also use pow(2,lh) in c++

[@dreamyme543]

Understood:)

[@arpanbanejee5143]

I could not understand how the TC Is O(logn^2) for the worst-case. even if we apply the formula, for calculating the left and right height we are traversing through all the nodes for the right part. Someone pls help me.

[@takeUforward]

Complete binary tree height is always log n.

[@thilakreddy1904]

Bhai Graphs ke bad Ek video Bit manipulation ke bareme banao na...

[@we_crood]

should be 1

[@sujan_kumar_mitra]

Understood

[@yuvrajkumar3765]

Guyz we are finding left most height and right most height we are not finding general left height and right height

[@AmanKumar-dh8md]

Doesn't this traverse all the nodes while calculating height?

[@stephen9726]

Nope. While finding height we just keep on going on one side. If we're finding left height we just keep on going left till we find a NULL and we don't move to right.

[@chhadios9959]

what if 5 has only one node the height will be the same but the formula won't work right?

[@037_abhinavkumar3]

same doubt

[@ravipatel-xu5qi]

we are traversing each node to get the heights of left or right part. So all N nodes are traversed. Even in normal pre order or post order traversal also we can count this number of nodes. Why to go for this approach.

[@spicy46475]

becaus it has less time complexity

[@pranavkorhale5089]

I have a small query in java code. when you call the getHeightRight or getHeightLeft Function why do you write while(root. left!=null) --It does not give actual height of the left side why not like this while(root!=null) -- it gives correct height //your code is working fine. //above query ate my head.

[@nishchaysingh804]

I have a doubt that bhaiya wrote if (left != right) --> this mean that the tree is not complete but in the question it is given that the tree is complete??

[@fazilshafi8083]

JAVA SOLUTION ⏬ class Solution { private int calculateLeftHeight(TreeNode node){ if(node == null){ return 0; } int count = 0; while(node.left!=null){ count++; node = node.left; } return count; } private int calculateRightHeight(TreeNode node){ if(node == null){ return 0; } int count = 0; while(node.right!=null){ count++; node = node.right; } return count; } public int countNodes(TreeNode root) { if(root==null){ return 0; } int leftH = calculateLeftHeight(root); int rightH = calculateRightHeight(root); if (leftH == rightH) { return (2

[@kotipallimadhumeher71]

can anyone tell what is exact meaning of the height of a tree? What i have know that the height is the longest path where no of EDGES are from a particular node to any leaf node. But according to this video,he represented height with no.of NODES not EDGES

[@neerajmahapatra5239]

Actually, you can think both the way it never matters.

[@omkarlavangad1434]

It depends on what is required in the question. Generally it should be the number of levels i.e. number of nodes, however you may be asked/need to calculate number of edges in some questions

[@ajayypalsingh]

💚

[@deepaksingh-qd7xm]

ok my question is if we are traversing the complete tree to find the height of tree why not count the nodes in same only its the same thing ???????????????????????? 🙄🙄🙄🙄🙄🙄🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔