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

Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements

[@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 🔥

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

[@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); } }

[@sakshigupta7616]

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

[@naveenkumarjadi2915]

Great Explanation bro , thank you for this series

[@stith_pragya]

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

[@paragroy5359]

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

[@cinime]

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

[@iampatelajeet]

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

[@rishabhkumar8115]

Great explanation & crisp code just what striver do

[@vedbhanushali608]

thank you sir great explanation.

[@arijitdey8419]

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

[@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!!!

[@MilindBasavaraja123]

Awesome Explanation. Leetcode solution was intimidating.

[@harisrashid0773]

Loved it solved on my own

[@jayasuryam3976]

If anyone struck here , see this (2

[@AvikNayak_]

sukriya!!!

[@adebisisheriff159]

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

[@vrandakansal5940]

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

[@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

[@shastriamisha]

Great Great Explanation..Thank you

[@bhaveshkumar6842]

Why is it return (1

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

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@manasranjanmahapatra3729]

This nice intuition really liked it.

[@aryanyadav3926]

Amazing video!

[@rishabhkumar8115]

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

[@nagavedareddy5891]

Huge Respect...❤👏

[@gouravkushwaha3001]

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

[@TarunKumar-cn6in]

Thanks so much sir🙏

[@prateekjain7623]

you are superb sir

[@vrandakansal5940]

Greatt explanation....🙏🙏

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

[@lavanyaprakashjampana933]

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

[@laveshgarg2189]

Great approach bhaiya maza aa gaya

[@krishnavamsichinnapareddy]

Understood 👍 Time complexity explanation is really good

[@kavatishivakumar1733]

can u explain why time complexity logn^2?

[@AdityaKumar-be7hx]

Buddy, you are amazing!

[@rishabhgupta9846]

understood,awesome striver

[@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?

[@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

[@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

[@jk-sm6qr]

thanks

[@hapysethi1306]

Thanks brother!

[@chiragbansod8252]

UNDERSTOOD

[@gowreeManohar]

got it sir thanks a lot

[@alesblaze4745]

thanks mate!

[@prajjwaldeepghosh7329]

Thank you

[@DurgaShiva7574]

Mauj kardi bhai ne.. 🔥🔥

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

[@UECAshutoshKumar]

Thank you sir

[@harshitjaiswal9439]

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.

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

[@aasthagoyal5059]

isme hm root k left me jakr uski height calculate krte, fr height-1 tk perfect tree hi hoga to (2^height-1) krke, ek level km tk ki nodes aajati or fr last level k liye root .right use krke nodes count krte or fr dono ko add ......ese nhi krskte kya?? static int height= 0; static int sum= 0; public int countNodes2(TreeNode root){ TreeNode lastNode = countLevel(root); sum += (( 2

[@oqant0424]

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

[@aanchalmittal9897]

But in worst case as you explained each time we traverse to left we will also go to right part.. So how is it that we will traverse logn nodes?

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

[@dipanshut]

Understood!!

[@adityasaxena6971]

Great sirr

[@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

[@vardankaushik3941]

In case we have 10 node, won't this approach will traverse all the node to find the solution?

[@deepaksarvepalli2344]

Is it guaranteed that the left height and right height are equal they are completely filled?

[@takeUforward]

That is the definition of complete tree, since you going till the right most point to find the right height, so if the right most point exists, and its equal to left, then in between nodes have to be there na.

[@rohandevaki4349]

at 14:48 , you are actually traversing the subtree to find the height right? why doesnt that count?

[@raviraj-xq4ue]

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

[@dreamyme543]

Understood:)

[@sujan_kumar_mitra]

Understood

[@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

[@subramanyah9848]

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

[@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

[@sakshisinghal1669]

Hey striver, what if the tree which you had taken example of does not have 11? In that case the left height comes out to be 3 and number of nodes we will calculate would be 7 but actually it is 6. Can you or anyone correct me if I missed anything?

[@chinthaladurgapranathi8975]

TreeNode cur=root; int left=0;int right=0; while(cur!=null){ left++; cur=cur.left; } cur=root; while(cur!=null){ right++; cur=cur.right; } if(left==right)return (int)Math.pow(2,left)-1; else return countNodes(root.left)+countNodes(root.right)+1;

[@sampathrakesh425]

The right height would be 2.. Since we're taking the right most node for calculating the height

[@kartikeysharma8904]

in that case the recursive call will function as we don't have equal leftHeight and rightHeight.

[@arpitkhanulia7]

here we are calculating right height and left height , not max height of left and max height of right;

[@shubhrajyotipoddar1684]

explanation is kinda iffy, actually in code left height is from the left most node not left subtree( height if it were a left skew tree) and similarly for right height it calculates height from the right skew tree not the right sub-tree, thus if left skew height and right skew height is same it means no of nodes is 2^n-1 as it is complete BT. Hope you understand.

[@thisismr900]

can someone explain this: @9:16 without traversing any nodes below the node-2, how can directly know height and hence return 7

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

[@shreyarawatvlogs6920]

Cant we directly write 1+ countnodes(root->left)+ countnodes(root->right). Its getting accepted in leetcode. Why to complex it and find height and all

[@notNotShivam]

That will be O(n). We're supposed to do it in less than O(n)

[@parasjaggi268]

in the ex u take ,remove 11 and find lh for 2 its 3 and rh is 3 so u would say 2^3-1=7 but as there no 11 so ans should be 6 ,rather than 7 as just with height how can u say it full

[@ashitapahwa7595]

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

[@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; } };

[@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??

[@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 ???????????????????????? 🙄🙄🙄🙄🙄🙄🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔🤔

[@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

[@judgebot7353]

good algo

[@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

[@ASHISHKUMAR-jh9kw]

In JAVA code there should be ((1

[@sulthanmogal9692]

also i think..it shud be 1

[@ranjeet_sohanpal]

Can somebody explain the Time Complexity point?

[@thilakreddy1904]

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

[@mriduljain1981]

completed lecture 32 of free ka tree series.

[@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

[@naivedhshah2980]

how is it better than recurcive solution?

[@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)

[@avi7474]

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

[@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

[@gigachad2419]

Striver is Literally God for DSA.

[@siddarthreddykoppera5930]

I have got a doubt, that is If there is a node connected to 6 then we get LeftHeight==RightHeight==3 and the answer will be (2^3-1=7): 1+7+7=15 which is wrong. Did I do any mistake or forgot to consider something? Please Help!!

[@Rohitkumar-me1uc]

same doubt

[@AmanSingh-on4ce]

how? left height is 3 and right height is 2 even when u add to node(6)

[@herculean6748]

if 6 nodes connected, then left height(extreme left) will be 3 and right height(extreme right) will be 2 lh != rh then 1 + countNodes(root->left) + countNodes(root->right) 1+3+2 (it will return)

[@dipeshsaili4468]

on leetcode, with O(N) time is 50 ms but using O(log^2N) it's 75 ms :C

[@yadneshkhode3091]

the time on leetcode is based on anything but time complexity

[@virusdgamer8804]

what if the leaf right is not there on a right subtree parent but the parent left subtree is full? In the given example...if node with value 11 is not there...node 2 will give both left and right heights to be 3, but since there is no 11, the number of nodes will not be 2^height - 1 Edit: I saw the technique that he used to find the height and that solves the above problem. This is not the traditional way of finding height of the tree, otherwise it would have killed the point of improving the time complexity anyways.

[@raunak1833]

thanks

[@letsrock7354]

At 5:54 what if 9 and 10 were not there then as per our code it would give equal height..right? correct me if I m wrong

[@someshpatel7660]

Yes exactly. Thats what I was wondering about. Complete BT might not have right sibling but height will still be same in that case, this formula might be wrong?

[@tusharnain6652]

In strivers code, when we passes root to getHeight function, isnt that gonna change root to NULL. Take a look at that please!

[@princiagrawal1428]

I guess not because we are not passing the root by reference

[@tusharnain6652]

@@princiagrawal1428 my bad

[@shashamnk2525]

Do we know the explanation of Bitwise leftshift operation is done on 1 in CPP and 2 on JAVA ? I am not sure why we are using 2

[@shashamnk2525]

So i did some digging if the height of root is considered 0 then formula for total number of nodes is 2^(h+1) -1, if the height of the root is considered 1 then the formula is 2^h -1.

[@mdrehankhan3458]

it will be 1

[@shashamnk2525]

@@mdrehankhan3458 yes if we are counting height from zero then yes

[@ishaankaustav727]

💚💚💚