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

  • @anonymoussingh5017
    @anonymoussingh50173 жыл бұрын

    best explanation on youtube!! nobody explains recursion like you.. Thanks a lot...your channel is underrated

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Thanks. So nice of you :)

  • @anonymoussingh5017

    @anonymoussingh5017

    3 жыл бұрын

    @@FitCoder if possible , try to make solution of burning tree problem from gfg practice.geeksforgeeks.org/problems/burning-tree/1.. thanks

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Yes...soon

  • @rishabhjajoriya2821
    @rishabhjajoriya28212 жыл бұрын

    great...grateful to have a mentor like you

  • @FitCoder

    @FitCoder

    2 жыл бұрын

    thank you 🙏

  • @JoffreyB
    @JoffreyB2 жыл бұрын

    Best explanation step by step! Love it! Good job and thank you

  • @FitCoder

    @FitCoder

    Жыл бұрын

    Welcome :)

  • @manavshah7450
    @manavshah74503 жыл бұрын

    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

    @FitCoder

    3 жыл бұрын

    Noted.

  • @kunalmodi6814
    @kunalmodi68143 жыл бұрын

    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

    @FitCoder

    3 жыл бұрын

    Thanks. Glad it helped :)

  • @DeepakSaini7900
    @DeepakSaini79003 жыл бұрын

    Gazab Sir

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @FitCoder
    @FitCoder3 жыл бұрын

    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

  • @heyyman186
    @heyyman1863 жыл бұрын

    so many ways to solve a single problem with dry run. subscribed! ty

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @harimerugu8812
    @harimerugu88122 жыл бұрын

    great explanation keep continue bro

  • @FitCoder

    @FitCoder

    2 жыл бұрын

    thanks :)

  • @amandatao9622
    @amandatao96223 жыл бұрын

    This is actually quite a good explaining!!! thumbs up!

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @prashanthchinthilla3968
    @prashanthchinthilla39683 жыл бұрын

    The first approach is awesome 💯💯💯

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Thanks :)

  • @amishaverma4097
    @amishaverma40973 жыл бұрын

    Very nicely explained!

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @codingninja3123
    @codingninja31233 жыл бұрын

    I hit like button whenever I see an upload from you. I owe my ds knowledge to you 👍

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    So nice of you :)

  • @ritesh3044
    @ritesh30443 жыл бұрын

    Amazing , I am gonna refer to your channel for my further doubts in concepts :-)

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @kribcrab
    @kribcrab3 жыл бұрын

    Great explanation man , keep up the good work

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @raj1307
    @raj13073 жыл бұрын

    Great explanation!

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @SHASHANKRUSTAGII
    @SHASHANKRUSTAGII3 жыл бұрын

    beutiful explanation bro

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @yashmathur1389
    @yashmathur13893 жыл бұрын

    Very Good Explanation

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @devlead6114
    @devlead61143 жыл бұрын

    Excellent explanation

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks 🙏

  • @shaheenrafiq5974
    @shaheenrafiq59743 жыл бұрын

    Great explanation. Gonna refer to your channel for more vids :))

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Thanks :)

  • @tecHSonic
    @tecHSonic3 жыл бұрын

    Dude God explanation. Please upload more videos on interview topics and preparation. Keep up the good work.

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks. Will do :)

  • @ChandraShekhar-by3cd
    @ChandraShekhar-by3cd2 жыл бұрын

    Thanks for the great explanation. Please upload more videos on Leetcode problems.

  • @FitCoder

    @FitCoder

    2 жыл бұрын

    Sure I will

  • @tkishore1260
    @tkishore12603 жыл бұрын

    Superb

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thanks :)

  • @ayushkumarjha5851
    @ayushkumarjha58513 жыл бұрын

    superb sir!! awesome work.This was the video that i needed thank you sir and good to know you are from pec chandigarh

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @suhasmallya7192
    @suhasmallya71923 жыл бұрын

    very well explained sir

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    thank you :)

  • @ok_7566
    @ok_75662 жыл бұрын

    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

    @FitCoder

    2 жыл бұрын

    Great...put daily some effort both in coding and fitness...you will attain both 👍

  • @sumitjindal1115
    @sumitjindal11153 жыл бұрын

    Sir please make video on this question construct binary tree from string

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Soon :)

  • 3 жыл бұрын

    Sir that morris traversal isn't working Plzz help!

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Can you paste the entire code using morris traversal and which example is failing?

  • @parthpandya2909
    @parthpandya29092 жыл бұрын

    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)

  • @jaydipbarvaliya
    @jaydipbarvaliya3 жыл бұрын

    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

    @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

    @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

    @FitCoder

    3 жыл бұрын

    Yes...if all are pointers

  • @ShubhamTiwari-ks2qg
    @ShubhamTiwari-ks2qg3 жыл бұрын

    approach 1 doesn't work in python why?

  • @FitCoder

    @FitCoder

    3 жыл бұрын

    Should work...logic is language independent.