Flatten Binary Tree to Linked List | 3 Methods Explained | Trees
In this video, I have discussed how to flatten a binary tree to linked list. The "linked list" should be in the same order as a pre-order traversal of the binary tree.
I have explained 3 methods to flatten the tree:
First is the recursive method in which the traversal is done as Right-Left-Root, which is also sometimes referred as reverse postorder traversal.
Second method uses stack and has space and time complexity of O(n)
Third method is somewhat similar to Morris traversal and is efficient with space complexity of O(1) and time complexity of O(n)
Source code: github.com/fit-coder/fitcoder...
00:00 Introduction
00:05 What is flattening a binary tree?
00:49 Method 1: Using recursion
07:10 Method 2: Using stack
12:23 Method 3: Efficient O(1) space
11:51 Implementation
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For other tree tutorials, please refer to the below links:
Introduction to Trees: • Introduction to Trees ...
Binary Trees: • Introduction to Binary... &t=8s
Binary Tree Traversals: • Binary Tree Traversals... &t=64s
Shortcut trick for Binary Tree Traversals: • Shortcut Trick for Bin...
Inorder Traversal Iterative: • Inorder Traversal of B...
Preorder Traversal Iterative: • Preorder Traversal of ...
Postorder Traversal Iterative (2 stack method): • Postorder Traversal of...
Postorder Traversal Iterative (1 stack method): • Postorder Traversal of...
Level Order Traversal: • Level Order Traversal ...
Morris Inorder Traversal: • Morris Inorder Travers...
Zigzag Level Order Traversal: • Zigzag (Spiral) Level ...
Binary Tree From Inorder and Preorder (Recursive): • Construct Binary Tree ...
Binary Tree From Inorder and Preorder (Iterative): • Construct Binary Tree ...
Binary Tree From Inorder and Postorder (Recursive): • Construct Binary Tree ...
Binary Tree From Inorder and Postorder (Iterative): • Construct Binary Tree ...
Binary Tree From Inorder and Levelorder: • Construct Binary Tree ...
Binary Tree From Preorder and Postorder: • Construct Full Binary ...
Height of a Binary Tree (Recursive): • Height (Maximum Depth)...
Height of a Binary Tree (Iterative): • Height (Maximum Depth)... &t=385s
Diameter of a Binary Tree: • Diameter of a Binary T...
Lowest Common Ancestor: • Lowest Common Ancestor...
Left View and Right View (Recursive): • Left View and Right Vi...
Left View and Right View (Iterative): • Left View and Right Vi...
Top View and Bottom View (Recursive): • Top View and Bottom Vi...
Top View and Bottom View (Iterative): / =-cr4i8ztxgc
Boundary Traversal: • Boundary Traversal of ...
Vertical Order Traversal: • Vertical Order Travers...
Diagonal Traversal: • Diagonal Traversal of ...
For in-depth Graph theory and implementation details, please refer to the below playlist:
• Introduction to Graphs... &list=PLFj4kIJmwGu3m30HfYDDufr3PZBfyngr0
#DataStructure,#Trees,#FitCoder,#Algorithm,#competitiveprogramming,#binarytree
Пікірлер: 64
best explanation on youtube!! nobody explains recursion like you.. Thanks a lot...your channel is underrated
@FitCoder
3 жыл бұрын
Thanks. So nice of you :)
@anonymoussingh5017
3 жыл бұрын
@@FitCoder if possible , try to make solution of burning tree problem from gfg practice.geeksforgeeks.org/problems/burning-tree/1.. thanks
@FitCoder
3 жыл бұрын
Yes...soon
great...grateful to have a mentor like you
@FitCoder
2 жыл бұрын
thank you 🙏
Best explanation step by step! Love it! Good job and thank you
@FitCoder
Жыл бұрын
Welcome :)
Instead of just dry running please describe and explain the intuition, thought process and how to build the logic. Thats what will come in handy when we solve questions by ourselves. Thanks.
@FitCoder
3 жыл бұрын
Noted.
amazing tutorial. I really liked how you explained and also at first you gave an idea what the question asked and why we need to use post-order. Now whenever a question of this variation comes, this technique will click for sure. Thank you once again.
@FitCoder
3 жыл бұрын
Thanks. Glad it helped :)
Gazab Sir
@FitCoder
3 жыл бұрын
thank you :)
00:00 Introduction 00:05 What is flattening a binary tree? 00:49 Method 1: Using recursion 07:10 Method 2: Using stack 12:23 Method 3: Efficient O(1) space 11:51 Implementation
so many ways to solve a single problem with dry run. subscribed! ty
@FitCoder
3 жыл бұрын
thank you :)
great explanation keep continue bro
@FitCoder
2 жыл бұрын
thanks :)
This is actually quite a good explaining!!! thumbs up!
@FitCoder
3 жыл бұрын
thanks :)
The first approach is awesome 💯💯💯
@FitCoder
3 жыл бұрын
Thanks :)
Very nicely explained!
@FitCoder
3 жыл бұрын
thank you :)
I hit like button whenever I see an upload from you. I owe my ds knowledge to you 👍
@FitCoder
3 жыл бұрын
So nice of you :)
Amazing , I am gonna refer to your channel for my further doubts in concepts :-)
@FitCoder
3 жыл бұрын
thanks :)
Great explanation man , keep up the good work
@FitCoder
3 жыл бұрын
thank you :)
Great explanation!
@FitCoder
3 жыл бұрын
thanks :)
beutiful explanation bro
@FitCoder
3 жыл бұрын
thanks :)
Very Good Explanation
@FitCoder
3 жыл бұрын
thanks :)
Excellent explanation
@FitCoder
3 жыл бұрын
thanks 🙏
Great explanation. Gonna refer to your channel for more vids :))
@FitCoder
3 жыл бұрын
Thanks :)
Dude God explanation. Please upload more videos on interview topics and preparation. Keep up the good work.
@FitCoder
3 жыл бұрын
thanks. Will do :)
Thanks for the great explanation. Please upload more videos on Leetcode problems.
@FitCoder
2 жыл бұрын
Sure I will
Superb
@FitCoder
3 жыл бұрын
thanks :)
superb sir!! awesome work.This was the video that i needed thank you sir and good to know you are from pec chandigarh
@FitCoder
3 жыл бұрын
thank you :)
very well explained sir
@FitCoder
3 жыл бұрын
thank you :)
you are the perfect guy I want to be I want to code and be fit as well!!!! you need more ype ypu are great!
@FitCoder
2 жыл бұрын
Great...put daily some effort both in coding and fitness...you will attain both 👍
Sir please make video on this question construct binary tree from string
@FitCoder
3 жыл бұрын
Soon :)
Sir that morris traversal isn't working Plzz help!
@FitCoder
3 жыл бұрын
Can you paste the entire code using morris traversal and which example is failing?
In this code i'm not clear how to use global variable it is giving error (pre is not defined in r.right=pre line). plzzz answer if u know class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ pre=None def fun(r): global pre if r!=None: fun(r.right) fun(r.left) r.right=pre r.left=None pre=r fun(root)
HUGE thanks for tutorial sir, however In Approach 2 --The thing which really perplexed me is that, you are doing operation with CURR variable and in the every time you are assigning the new value from stack by popping element from Stack then how actual tree is impacted ? call by reference or anything which I'm missing then make me correct,
@FitCoder
3 жыл бұрын
The curr variable is a pointer...so it is pointing to the same address as the tree node...so any modifications done on it affect the tree
@jaydipbarvaliya
3 жыл бұрын
@@FitCoder this means if we push any node into Stack and then again pop from that Stack and then we modify that node then will it still point to the same address as the tree node, RIGHT SIR?
@FitCoder
3 жыл бұрын
Yes...if all are pointers
approach 1 doesn't work in python why?
@FitCoder
3 жыл бұрын
Should work...logic is language independent.