L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[vedantsharma]

This series is not best just because of the quality content, but also the way Striver has organized this playlist. The previous video was Morris Traversal, and this is the application of the Morris Traversal. You definitely are a gem Striver ❤

[Jai_Jai_shri_Ram]

in 3rd approach please add this line curr->left=NULL in the if block, after curr->right=curr->left;
if you don't it give run time error:

[samridhshubham]

I've referred to so many channels over my lifetime, ngl...this guy is just GOAT.

[RishiMishra]

Your video lectures are very good and I am really thankful that you are providing us the free content.
I think you forgot in the last pseudocode(approach 3) cur->left=NULL and due to that some of the viewers may have the confusion that's why I am writing this comment.

Node *cur=root, *prev=NULL;
while(cur!=NULL){
if(cur->left!=NULL){
prev=cur->left;
while(prev->right){
prev=prev->right;
}
prev->right=cur->right;
cur->right=cur->left;

cur->left=NULL; //this line
}
cur=cur->right;
}

And thanks again for such quality content.

Edit :- Some of the viewers has already wrote this in the comment and code which you gave is also correct.

[santhoshm]

Striver you are the GOAT 🔥

Before seeing this video, i thought i can create new nodes to flatten BT to LL. But after watching this thought process i was shocked.. With this i completed the Binary Tree playlist, next i will start Binary Search Tree.

[alesblaze]

bro after watching your previous videos from this tree series and til 2:16 only i watched this video, i was able to come up with an approach and solved it iteratively. thanks a lot.

Code :
class Solution {
public void flatten(TreeNode root) {
TreeNode temp = root;
if(temp == null) return;
Deque<TreeNode> stack = new LinkedList<>();

while(temp != null || !stack.isEmpty()) {
TreeNode prev = null;
while(temp != null) {
if(temp.right != null) {
stack.push(temp.right);
}
temp.right = temp.left;
temp.left = null;
prev = temp;
temp = temp.right;
}

if(!stack.isEmpty()) {
TreeNode nextRight = stack.pop();
prev.right = nextRight;
temp = nextRight;
}
}
}
}

[pulkitchausali]

One of the best explanation from striver
In Approach 3
after if block ends add one line
cur.left = null;
otherwise output will be wrong as left pointer is pointing to its original left child

[shayanshahini]

Another great explanation, Thanks Striver. The 4th brute force and intuitive approach is to do the preorder and store all the nodes in an array and then update point the right of each node to the next node in the array and nullify the left pointer, the code is here if anyone interested. This has O(N) space complexity due to the storing of the all the nodes and then go through them.
res = []
def dfs(node):
if not node:
return

res.append(node)
dfs(node.left)
dfs(node.right)

dfs(root)


for i in range(len(res)-1):
node = res[i]
node.left = None
nextNode = res[i+1]
node.right = nextNode

[jaditi]

This is what passion speaks like.Gets straight to the heart.I was finding hard to understand this concept.Thankyou so much Finally found someone to get the intuition behind algos.This is the first video of yours and subscribed right away.Just keep going.

[rishabhkumar]

all 3 approaches are owsome!!!! and the 3rd one using linked list blows
all 3 approaches are owsome!!!! and the 3rd one using linked list blows

[deepaksarvepalli]

How it is possible for you man! You always come up with such blowing solutions.

[sparshsharma]

Amazing explanation bhaiya! Just one doubt, I think while recording, you forgot to set the left pointers of nodes to null in morris traversal.
Edit: The code links in the description are 100% working and correct.

[satakshipal]

You have arranged this playlist series in best order. It is really very helpful.

[ANANDKUMAR-jkyp]

Striver Bhaiya, the same question was asked in my DE Shaw Interview. Unfortunately, couldn't answer that. Kaash, pahle dekh liya hota aapka yeh video. Anyways, thank you for your amazing explanation.

[sameekshamurdia-yeariddph]

Congrats guys for completing Binary Trees, ab BST start krte h 🥳🥳
Thank you so much striver bhaiya for the amazing series💖

[rushidesai]

First approach is pretty smart solution. Crisp.

[Dontpushyour_luck]

did it with morris traversal even before watching the video. you taught us so good!

[shivangisrivastava]

literally never thought we could do this question so easily!! i am blown! that too with 3 simple approaches!

[shamanthhegde]

I coded this by myself
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return None
curr = root
while curr:
if curr.left is None:
curr = curr.right
else:
rightTree = curr.right
leftTree = curr.left
curr.left = None
curr.right = leftTree
while leftTree.right is not None:
leftTree = leftTree.right
leftTree.right = rightTree


Time complexity: O(n)
space complexity: O(1)