L8. Level Order Traversal of Binary Tree | BFS | C++ | Java

[@takeUforward]

If you understand, pleaseeeeee like and subscribeeeee :) Do follow me at Insta: striver_79

[@genzsubh]

Nhi Samjhe to Dislike Bhi Likh Deta ..

[@ajaykathwate7595]

@@genzsubh Le, I disliked your comment!

[@sayantaniguha8519]

Why is the space complexity, O(n) & not the maximum number of nodes in any single level of the tree?

[@dishikasingh235]

This series is a blessing for all those who find tree difficult...Please make series on every DS...Great Job!

[@Mohit_Q]

where are you working now ?

[@TON-108]

@@Mohit_Q bss kr bhai 😂😂

[@rickseth9207]

@@TON-108 kya kiya tere bhai ne?

[@TON-108]

@@rickseth9207 Jaise koi ladki dikhi tut padte hai londe 😂😂

[@rickseth9207]

@@TON-108 no actually yeh wala normal laga, mujhe pata hai inn sab videos mai bhi ladkiyon ke comments mai simps aate hai but yeh wala simp nahi tha.

[@divyanshmishra5121]

Recursive Solution using BFS: vector ans; void help(TreeNode *root,int depth) { if(root==NULL) { return; } if(ans.size()==depth) { ans.push_back(vector()); } ans[depth].push_back(root->val); help(root->left,depth+1); help(root->right,depth+1); } vector levelOrder(TreeNode* root) { help(root,0); return ans; }

[@HomiePlaysYT]

Java soln using Recursion without any queue: public List levelOrder(TreeNode root) { List ans = new ArrayList(); travel(0, root, ans); return ans; } private void travel(int level, TreeNode cur, List ans) { if (cur == null) return; // add another list only when we visit a new level for the first time if (level >= ans.size()) ans.add(new ArrayList()); ans.get(level).add(cur.val); // get the list of that level add the node val to it travel(level + 1, cur.left, ans); travel(level + 1, cur.right, ans); }

[@fantasyillusion]

For those looking for python code # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ans=[] if root==None: return ans queue=deque([root]) while queue: n=len(queue) level=[] for i in range(n): node=queue.popleft() if node.left!=None: queue.append(node.left) if node.right!=None: queue.append(node.right) level.append(node.val) ans.append(level) return ans

[@gunahawk6893]

def levelOrder(self): if self.root == None: return else: self._levelOrder(self.root) def _levelOrder(self,curNode): q = [] q.append(curNode) while len(q) != 0: curNode = q.pop(0) print(curNode.value , end= " ") if curNode.left != None: q.append(curNode.left) if curNode.right != None: q.append(curNode.right)

[@Rahul_Mongia]

😅

[@banothutharun2743]

what a fentastic explaination sir. simply superb

[@krishnasudan3410]

Just started it and loving it.. On point clear explanation.. No khich khich... No time waste.. Worth watching.. ♥️

[@SB-hb2kx]

The expaination was so good that even after 6months I was able to solve it without help. Thank you @Striver bhaiya

[@PriyaGupta-sg4sm]

No one has ever made level order this easy!

[@susmitapatil4847]

He is the best tutor. Good job

[@lifehustlers164]

9/54 (16% done)!!!

[@kermitdaphrogge525]

Are you now placed, brother?

[@vganesh9829]

Understood Striver!😊

[@cinime]

Understood! Super gorgeous explanation as always, thank you very much!!

[@vedantsharma5876]

Striver you are a boon to us Tier 3 Students :') Love you man!

[@AdityaChaturvedi-2005]

Not only tier 3 students bro . He is a boon for everyone learning dsa

[@RitikKumar-bk6pj]

Sir aap bahut bhadiya pdate ho thank u for making this series

[@sukritikuila9161]

Shouldn't be the Space Complexity : O(width) cause the queue can grow upto max nodes in a level ?

[@manavshah7450]

Understooooood!!! Awesome explanation. Please upload all videos by tomorrow, else after weekend u will get buzy with office :/

[@PrashantSingh-jy6zp]

for best experience go to 0:41

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@averylazyandweirdhuman]

I want to be hard working like you. You really live up to your channel name. ✌️

[@shake-her3908]

vector levelOrder(Node* node) { vector ans; queueq; q.push(node); while(!q.empty()){ //solving in hard way int size =q.size(); for(int i=0;ileft){ q.push(front->left); } if(front->right){ q.push(front->right); } ans.push_back(front->data); } } return ans; }

[@yashshah660]

I have also written the same code but I got a wrong answer on GFG

[@lourduradjou182]

superb bhai

[@mayanksaurabhmayanksaurabh9271]

very well explained. thanks a ton

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@apmotivationakashparmar722]

Thank you so much striver.

[@rajeshwari.s.r9703]

Thanks a lot …I understood very clearly✌🏻 dsa playlist helped a lot for me 😇😊🤩

[@AkshayKumar-oi2cu]

No one can teach like u ...sir

[@codeman3828]

Understood

[@stith_pragya]

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

[@atharvakulkarni2024]

Tablet Lectures are much much effective..Thanks a lot !!DP SERIES PLEASE

[@nikitakeshri9233]

beautifully explained

[@yashkhatwani3198]

love you, bless you, thank you.

[@FusionArcs]

You really are amazing at explaining things. Thanks, brother.

[@deeptimayeemaharana2448]

a for loop is there inside the while loop so how is the time complexity O(n)

[@srirambharadwaj1937]

amazing explanation bhaiya

[@bhavkushwaha]

Thankyou Striver, Understood!

[@utsavseth6573]

Superb Work RAJ.

[@SatyamKumar-bw4vi]

Hare Krishna!

[@md.imrankhan6912]

Great Striver

[@ram_pande8039]

you are doing a really great and self-less work. may you achieve all successes.

[@samuelfrank1369]

UNDERSTOOD. THANKS A LOT

[@deepikasrivastava3040]

Thank you for the valuable and explanatory content.

[@aadeshsharma0001]

Bhaiya code is really very clean

[@rohitmittal514]

Thanks bhai bhot help milti iss course se. Keep making such videos. Aur ek request h DBMS ka course bhi daal do.

[@AtharvaRao0104]

A good teacher will tell why we need a queue to solve this.. here the teacher directly states to do a BFS we need a queue .. I'm sure a lot of people would not be able to explain from first principles ..

[@hashcodez757]

Understood Striver!!

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@sarangkumarsingh7901]

Awesome................

[@duckworth_lewis]

Thx thx thx

[@parul8334]

understood ❤❤ love u sir 🥰🥰

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@shubhamgite7730]

thank u so much bhayya for this very important tree series & your explanation is at next level yarr bahot Simply samzaa dete hoo..🤗🤗

[@sayantaniguha8519]

Why is the space complexity, O(n) & not the maximum number of nodes in any single level of the tree?

[@sayantanmanna1360]

i.e. O(2*d), where 2 is the branching factor and d is the max level

[@hetpatel1772]

The Best Series on Tree

[@nitantjoshi9903]

In java why we did List wrapList = new LinkedList() instead of just using List list = new ArrayList(); And yes why q.offer() instead of using q.add() ?

[@nipunsinha7445]

q.add() will throw an exception if an insertion fails, so you will have to wrap it in a try-catch block...q.offer() returns a boolean to indicate if insertions was successful or not. More explaination here docs.oracle.com/javase/tutorial/collections/interfaces/queue.html - Check the Queue Interface structure table on this page.

[@koushikvss7638]

q.add() will throw an exception when there is no capacity to add more elements, whereas q.offer() will just return false.

[@shashankkr1008]

Clearly understood and coded, Thanks bhaiya!!!

[@pritishpattnaik4674]

Beautifully explained , amazing

[@premsagargupta5263]

Thank you brother, learning trees from your series, very helpful :)

[@Ashutosh.369]

you wrote a lengthy code in java. we can use an arraylist to store the elements while traversing. here is the code how i have implemented void level_order( Node root ) { if( root == null ) return; ArrayList ans = new ArrayList(); // to store the elements Queue q = new ArrayDeque(); q.add( root ); while ( !q.isEmpty() ) { Node temp = q.poll(); if( temp.left !=null ) q.add( temp.left ); if( temp.right !=null ) q.add( temp.right ); ans.add( temp.data ); } System.out.println( ans ); } Narayan Narayan 😇😇

[@Sungod.aditya]

the function needed to return List

[@owaisch3442]

is it possible to find the level of a node using preorder traversal?

[@eiji11282]

Sir why do we not using single vector and why do we use vector of vector???

[@Tbm4545]

Is the levels needed ?? Or we can simply use a stack and print by sequnce.

[@krentwhite2668]

This video is used to solve Zigzag Level Order traversal also... Thanks Mr. Striver👏

[@DeadPoolx1712]

UNDERSTOOD;

[@shubamgoswami]

THAK GYA HU VROOO RELEVEL SUN SUN KE

[@AyushGupta-kp9xf]

Complexity analysis at 7:36

[@Mr.Indianwxvhehsy9191hghgx]

nice video sir

[@sayankarmakar13]

Thanks bhaiya for great explanation

[@ajaybachate7137]

if queue has n nodes inside it and we traverse for n nodes to put into vector then wont it be O(N^2) time complexity?

[@mriduljain1981]

completed lecture 8 of tree playlist.

[@debugagrawal]

Bhaiya ap abhi 1 hi approach bata rahe ho, Recusrion se bhi mast hota hai, so as per interview point of view both approaches batao, better for all students, thanks in advance ♥

[@LearnWithMe7777]

Understood❤

[@Ramu9119]

Nice Video Brother Keep it up

[@runtime379]

awsome lectures

[@72nishantwadhawan5]

Best Content on the internet.

[@rahulyadav8159]

variable levelNum is quite confusing in JAVA implementation.

[@asthapandey9587]

Couldn't understand Java code

[@wribo5433]

You are amazing brother! Thank you for all the hard work you put for us

[@shivanisinha7035]

Such an amazing video

[@divyanshuyadav5524]

While declaring Queue...What is significance of * in ?? Why can"t be it only ??

[@hakunamatata-nl4js]

Thank you

[@JohnWickea]

Thanks a lot

[@nagavedareddy5891]

Huge respect..❤👏

[@Versha_arya]

Thank you ao muchh

[@adebisisheriff159]

Understood!!!

[@NoxuzBlog]

thank you for the video

[@yatharthahuja1635]

amazing content😀

[@Ammaradreamart]

Best lecture

[@s_sattu_s]

is it a queue or stack? because the design looks similar to stack rather than queue

[@shrishshrivastava4444]

Clarity 🔥🔥

[@gandhijainamgunvantkumar6783]

Amazing video bhaiya :)

[@103himajapoluri6]

is bfs same as level order traversal

[@willturner3440]

why space complexity should not be O(width of tree) ?

[@singhs_aniket]

Understood 👌👌

[@Code_Solver]

Thank you Striver bayya

[@DhruvSharma-mh5vf]

Well explained 👊

[@elements8630]

Best video I could find!!! Great job, keep up the good work bhaiya :-)

[@ankitdubey9310]

@take U forward striver bhaiya ye question tha ki : recursion and backtracking mein jab aap sochte ho koi sawal karne ke liye to aap kya ek cycle pura imagine karte ho? ya fir thoughtprocess kaise hota hai, mujhe approach samajh mein aa jati hai recursion and backtrack questions mein par likha nahi aata , please guide me

[@gouravupadhyay9092]

same question bro

[@OtakuRiku]

Watch permutation and combination using backtracking... Most of the backtracking problem are based on that problem...

[@pranav288]

recursive leap of faith L bhai

[@MrMaharaj]

Level Order Traversal Approach in C++: int maxDepth(TreeNode* root) { if(root == NULL) return 0; vector answer; queue q; q.push(root); while(!q.empty()) { int size = q.size(); vector level; for(int i=0;ileft != NULL) q.push(currentNode->left); if(currentNode->right != NULL) q.push(currentNode->right); level.push_back(currentNode->val); } answer.push_back(level); } return answer.size(); }

[@Pritamdaspk]

It's the approach of finding the maximum depth of the tree.

[@ujjalbanerjee4372]

@@Pritamdaspk only the list line is different r8?

[@AB-iv4bq]

what is val??

[@laveshchanchawat6983]

int size = queue.size(); if we remove this line and directly use for(int i = 0; i < queue.size(); i++) why the output are different?

[@petermj2804]

because queue size will keep changing after popping each element,instead if we initialize the size before any of the elements are popped we don't have to worry about the queue size changing after each pop operation.

[@apoorvkumar1748]

Thank You So Much!

[@studynewthings1727]

understood