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: https://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 | Trees Tutorial | D...
Binary Trees: • Introduction to Binary Trees | Trees Tutor... &t=8s
Binary Tree Traversals: • Binary Tree Traversals | Inorder, Preorder... &t=64s
Shortcut trick for Binary Tree Traversals: • Shortcut Trick for Binary Tree Traversal |...
Inorder Traversal Iterative: • Inorder Traversal of Binary Tree without R...
Preorder Traversal Iterative: • Preorder Traversal of Binary Tree without ...
Postorder Traversal Iterative (2 stack method): • Postorder Traversal of Binary Tree Using T...
Postorder Traversal Iterative (1 stack method): • Postorder Traversal of Binary Tree Using O...
Level Order Traversal: • Level Order Traversal of Binary Tree | Usi...
Morris Inorder Traversal: • Morris Inorder Traversal of Binary Tree | ...
Zigzag Level Order Traversal: • Zigzag (Spiral) Level Order Traversal of B...
Binary Tree From Inorder and Preorder (Recursive): • Construct Binary Tree From Inorder and Pre...
Binary Tree From Inorder and Preorder (Iterative): • Construct Binary Tree From Inorder and Pre...
Binary Tree From Inorder and Postorder (Recursive): • Construct Binary Tree From Inorder and Pos...
Binary Tree From Inorder and Postorder (Iterative): • Construct Binary Tree From Inorder and Pos...
Binary Tree From Inorder and Levelorder: • Construct Binary Tree From Inorder and Lev...
Binary Tree From Preorder and Postorder: • Construct Full Binary Tree From Preorder a...
Height of a Binary Tree (Recursive): • Height (Maximum Depth) of a Binary Tree | ...
Height of a Binary Tree (Iterative): • Height (Maximum Depth) of a Binary Tree | ... &t=385s
Diameter of a Binary Tree: • Diameter of a Binary Tree | Trees
Lowest Common Ancestor: • Lowest Common Ancestor (LCA) in a Binary T...
Left View and Right View (Recursive): • Left View and Right View of Binary Tree | ...
Left View and Right View (Iterative): • Left View and Right View of Binary Tree | ...
Top View and Bottom View (Recursive): • Top View and Bottom View of Binary tree | ...
Top View and Bottom View (Iterative): / =-cr4i8ztxgc
Boundary Traversal: • Boundary Traversal of Binary Tree | Trees
Vertical Order Traversal: • Vertical Order Traversal of a Binary Tree ...
Diagonal Traversal: • Diagonal Traversal of a Binary Tree | O(n)...
For in-depth Graph theory and implementation details, please refer to the below playlist:
• Introduction to Graphs Data Structure &list=PLFj4kIJmwGu3m30HfYDDufr3PZBfyngr0
#DataStructure,#Trees,#FitCoder,#Algorithm,#competitiveprogramming,#binarytree